複雑さのクラスとアルゴリズムの複雑さの間の正確な関係 [重複]

Question

この質問にはすでに答えがあります:

• P、NP、NP コンプリート、NP ハードの定義は何ですか? 7 件の回答

多項式の時間計算量を持つすべてのアルゴリズムは P クラスに属しますか?そして、P クラスには多項式の複雑さを持たないアルゴリズムはありませんか?

非多項式の複雑さを持つすべてのアルゴリズムは、NP または NP-Hard、あるいはその両方に属しますか?

基本的な関係を理解し​​ようとしているだけです。

Answer 1

$P$ は、(TM または多項式等価モデルで) 多項式時間で解くアルゴリズムを持つ (決定) 問題のクラスとして定義されます。したがって、$P$ にはまさにこれらの問題が含まれており、それ以上でもそれ以下でもありません。

$NP$- に関しては、状況はより微妙です。$NP$ に多項式時間で実行される非決定性アルゴリズムがある場合、問題が発生します。同等の、よりユーザーフレンドリーな定義は、問題の解が与えられた場合、問題のサイズにおける時間多項式でその正しさを検証できるというものです。たとえば、ハミルトニアンであると主張するグラフとパスが与えられた場合、それが実際にハミルトニアン パスであることを多項式時間で検証できます。したがって、グラフにハミルトニアン パスがあるかどうかを判断する問題は $NP$ にあります。

説明:$NP$ は次のクラスです。 問題, 、のではありません アルゴリズム. 。アルゴリズムは $NP$ に属していません。

現在、いくつかの問題は多項式時間アルゴリズムを持たないことが知られています。これは、彼らが $NP$ にいるという意味ではありません。実際、いくつかの問題は $NP$ に存在しないことが知られています。たとえば、$NEXP$ の難しい問題です。

$NP$ 困難な問題については、$P=NP$ かどうかがわからないため、$P$ 以外の問題がすべて $NP$ 困難であるかどうかはわかりません。$NP=P$ の場合、すべての問題は $NP$ 困難です ($\Sigma^*$ と $\emptyset$ を除く)。

この回答 (これはかなり不完全です) は、基本的な複雑さのコースの約 3 週間の内容をカバーしています。シプサーの「計算理論」などの教科書を徹底的に読むことを検討してみてはいかがでしょうか。

Answer 2

多項式時間で何らかの決定問題を解くすべてのアルゴリズムは、問題が $P$ にあることを示します。しかし、$P$ の問題に対して多項式時間を必要としないアルゴリズムが確かに存在します。入力のすべての $n!$ 順列を生成して並べ替え、それぞれが並べ替えられているかどうかを確認できます。このアルゴリズムには指数関数以上の時間がかかりますが、問題は多項式時間で解決されます。