algorithm - 多項式時間で答えが得られる NP の例はありますか?

Question

ウィキペディアで NP と P を読んだところですが、2 つの質問があります。

1. NP の例を多項式時間で解くことはできますか?
2. 多項式時間で答えが得られる NP の例はありますか?</li>

Answer 1

免責事項：この回答は、多項式時間アルゴリズムが知られていない問題があるという事実に対処する実際的な側面に焦点を当てています。理論的な観点から正確な答えを出すには、質問で使用されている用語が十分に明確ではありません。

コンピュータ サイエンスにおける NP には、混同されやすい 2 つの意味があります。

(1) NP 完全問題のクラスとしての NP:

これらの問題のいずれに対しても、これまでのところ多項式アルゴリズムが見つかっています。このようなアルゴリズムが見つかれば、それぞれの問題を多項式時間で解くことができることが証明されています。NP 完全性の標準的な例は、巡回セールスマン問題です。

(2) 指数時間を必要とするアルゴリズムのプロパティとしての NP:

任意の NP アルゴリズムは、小さいサイズ N で解くことができます。問題は、計算の数が N とともに指数関数的に (つまり、非常に急速に)増加することです。

もともと NP アルゴリズムしか知られていない問題で、後に多項式時間アルゴリズムが見つかった問題があります。残念ながら、今は例を思いつくことができません。

NP 解しかない多くの問題に対して、最適解の適切な近似を生成する多項式時間アルゴリズムが存在します。多くのアプリケーションでは、これで十分です。