質問

とはどのような違いがあるのでしょうか？ NP , NP-完全 そして NP-ハード ?

私はウェブ上にある多くのリソースを知っています。あなたの説明を読みたいと思います。理由は、世の中にあるものと違うかもしれないし、私が気づいていないことがあるかもしれないからです。

どのように解決するのですか？

技術的な定義は理解するのに時間がかかるので、直感的に理解できる定義をお探しなのでしょう。まず、これらの定義を理解するために必要な予備知識を覚えておきましょう。

• 決定問題 : を持つ問題。 はい または いいえ の答えになります。

では、それらを定義してみましょう。 複雑性クラス .

P

Pは、多項式時間で解くことができるすべての決定問題の集合を表す複雑さクラスである .

つまり、問題のインスタンスがあれば、多項式時間でイエスかノーかの答えが決定できる。

例

連結グラフが与えられたとき G その頂点を2色で着色し、単色になる辺がないようにすることはできますか？

アルゴリズム：任意の頂点から始め、その頂点を赤、その近傍を全て青に着色し、続ける。頂点を使い果たすか、辺の両端を同じ色にせざるを得なくなったら止める。

NP

NPは、答えが「はい」であるインスタンスが多項式時間で検証可能な証明を持っているすべての決定問題の集合を表す複雑さのクラスである。

つまり、誰かが問題のインスタンスと、答えがイエスであることの証明書（証人と呼ばれることもある）を与えてくれれば、それが正しいかどうかを多項式時間でチェックすることができるのです。

例

整数の因数分解 はNPである。この問題は、与えられた整数 n と m という整数があるか？ f と 1 < f < m というように f を分割する。 n ( f は小さい係数で n )?

これは、答えが「はい」か「いいえ」であることから、決定問題です。もし誰かがこの問題のインスタンスを手渡したら（つまり、彼らは整数 n と m ) と整数 f と 1 < f < m と主張し f の因子である。 n (証明書)で答えを確認することができます。 多項式時間 を実行することで n / f .

NP-コンプリート

NP-Complete は、すべての問題の集合を表す複雑さのクラスである。 X NPの問題で、他のどのNPの問題も減らすことが可能である。 Y への X を多項式時間で表示します。

直感的には、これは Y の解き方がわかっていれば、すぐに X を早くしてください。正確には Y に還元される。 X 多項式時間アルゴリズムが存在する場合 f インスタンスを変換するために y の Y をインスタンスに x = f(y) の X に対する答えが多項式時間で得られるという性質があります。 y の答えがイエスである場合のみ、です。 f(y) は「はい」です。

例

3-SAT . これは、3項離脱型（OR）の接続詞（AND）が与えられた問題で、次のような形式の文です。

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

ここで各 x_vij はブール変数、または有限の定義済みリストの変数の否定です。 (x_1, x_2, ... x_n) .

を示すことができる。 すべてのNP問題は、3-SATに還元することができる . この証明は技術的なものであり，NP の技術的な定義 ( 非決定論的チューリング機械に基づく ). これは、以下のように知られています。 クックの定理 .

NP完全問題が重要なのは、そのうちの1つを解く決定論的多項式時間アルゴリズムが見つかれば、すべてのNP問題は多項式時間で解ける（すべてを支配する1つの問題）ことになるからです。

NP-ハード

直感的に、これらは以下のような問題である。 NP完全問題と同等以上の難易度 . ただし，NP困難問題は はNPである必要はない であり、かつ 決定問題である必要はない .

ここでいう正確な定義とは 問題 X がNP困難である場合、NP完全な問題が存在する。 Y というような Y に還元される。 X 多項式時間で .

しかし、どんなNP完全問題も多項式時間で他のどんなNP完全問題にも還元できるので、すべてのNP完全問題は多項式時間でどんなNP困難問題にも還元できる。そして、1つのNP困難な問題に対して多項式時間で解があれば、すべてのNP問題に対して多項式時間で解があることになる。

例

は 歯止め問題 は、NP困難な問題である。これは、あるプログラム P と入力 I 停止するのか？これは決定問題であるが、NPには入らない。NP完全問題はすべてこの問題に還元できることは明らかである。他の例として，どんなNP完全な問題もNP困難である．

私の好きなNP完全問題は マインスイーパー問題 .

P = NP

この問題は、コンピュータサイエンスで最も有名な問題であり、数理科学においても最も重要な未解決問題の1つである。実際、この問題は クレイ・インスティテュート は、この問題の解答に100万ドルを提供している（スティーブン・クックの 著作物 は非常に良い。）

PがNPの部分集合であることは明らかである。未解決の問題は、NPの問題が決定論的な多項式時間解を持つかどうかである。そうでないというのが大方の見方である。P = NP 問題の最新（そして重要性）についての優れた最近の記事を紹介します。 P対NP問題の現状 .

このテーマに関する最良の書籍は コンピュータと難解さ Garey and Johnson著。