最初のNP完全問題はどのようにNP完全であることが示されましたか？

Question

NP-Completeのウィキペディアエントリから：

＆quot;いくつかの新しい問題がNP完全であることを証明する最も簡単な方法は、最初にNPにあることを証明し、次に既知のNP完全問題をそれに還元することです ''

私はこれを理解していると確信しています：問題がある場合、NP完全であることを示すことができます：

1. NPにあることを示す（ 問題はで確認できます 上の多項式時間 非決定的チューリングマシン）

2. 既にNP完全であることがわかっている問題が、 新しい問題を「削減」

だから、私の質問は、最初のNP完全問題がどのようにNP完全であることを「証明」したのですか？かつて、既知のNP完全問題のセットはゼロであったに違いないため、上記のプロセスのステップ2に頼ることは不可能でした。

これは、私が知らない証明のための別の方法があると私に考えさせます。既知の多項式時間解法が存在しないため、特定の問題については、NP完全プロパティ全体が「想定」されます。 （実際、これを書いたので、そうだとしても驚くことはありませんが、どちらにしてもグルフィードバックをお願いします）。

Answer 1

クックの定理

クラスNPは、多項式時間で非決定性チューリングマシンによって決定可能な問題のクラスとして定義できます。この定理は、ブール式によって非決定性チューリングマシンの演算をエンコードすることにより、 SATがNP完全であることを示します。 >

歴史的に言えば、NP完全性の概念は、リチャードカープの独創的な論文で紹介されました（ 組み合わせ問題間の還元性 ）、NP完全性を定義し、クックの定理を使用し、1つの大きなショットでNP完全性の21の問題を証明しました。

Answer 2

証明の本質を伝えるために（Garey＆amp; Johnsonの Computers and Intractibility のいくつかのページは難しい）：

任意の計算問題はチューリングマシンとして表現できます。

特定の複雑さの制約を満たす、チューリングマシンを論理問題として表現することができます。

したがって、多項式時間で論理問題を解くことができれば、多項式時間でチューリング機械問題を解くことができます。

これは（他のいくつかの考慮事項と一緒に）多項式時間で論理問題を解決できる場合、多項式時間でNP問題を解決できることを示しています。これはNP完全の定義であるため、論理問題はNP完全であり、他の問題の基礎として使用できます。

使用される論理問題は、充足可能性（SATと略されることが多い）と呼ばれます。フォームの一連の節（Aまたはnot-Bまたはnot-C）（論理ORで接続された任意の数の命題と命題の否定で構成される節）が与えられた場合、すべてを行う命題に真理値の割り当てがあります句は本当ですか？

NP完全性は、明確に定義されたプロパティです。問題がNP完全であることに疑念を抱く唯一の理由は、別のNP完全問題を削減できると考えたが、まだ便利な問題を見つけることができず、証拠を導き出すことができていないことです。

問題は、NP完全問題が存在するかどうか、または問題がNP完全であることを証明する方法ではなく、それが何を意味するかです。 NP完全問題を解決するための多項式時間アルゴリズムを作成した人はいません。そのようなアルゴリズムが存在しないことを証明した人はいません。 P = NPであるかどうかにかかわらず、NP完全問題を解決するための優れたアルゴリズムはありません。

これはClaypool Foundationのミレニアム問題の1つです。そのため、非常に優秀な人々を何年も避けていた証拠を思い付くことができれば、100万ドルの費用がかかります。