第一個NP完全問題如何顯示爲NP完全？

Question

從對NP完全的維基百科條目：

「最簡單的方法來證明一些新的問題是NP完全是首先要證明它是NP，然後，以減少一些已知的NP完全問題它」

我敢肯定，我明白這一點：如果我有一個問題，我可以證明其是一個NP完全如果我：

1. 表明它是在NP（解決方案到 該問題可以在 多項式時間上驗證 非-deterministic圖靈機）的問題已經知道是NP完全

2. 顯示可以 「降低」新問題

所以，我的問題是，如何是第一NP-完整的問題「證明」是NP完全的？有一段時間，已知的NP完全問題的集合一定是零，並且這將使得在上述過程中不可能採取步驟2。

這讓我覺得有一種我不知道的證明方法。要麼是這樣，要麼是由於缺乏已知的多項式時間解決方案，因此對於某些問題可能會「假設」整個NP完全屬性。 （實際上，寫過這些，如果是這種情況，我不會感到驚訝，但是我希望以某種方式反饋一些guru反饋）。

Answer 1

Cook's Theorem

類NP可以被定義爲類的在多項式時間由非確定性圖靈機可判定的問題。這個定理表明，SAT是NP-complete，它是通過用布爾公式編碼任何非確定性圖靈機的操作，使得機器當且僅當該公式是SATisfiable時才接受。

從歷史上看，NP完全性的概念，在理查德·卡普的開創性論文（Reducibility Among Combinatorial Problems），在那裏，他定義的NP完全性介紹，使用庫克的定理，並在一個大人物，證明21個問題NP完全問題。

Answer 2

爲了讓你證明的本質（這是艱苦的幾頁將在Garey &約翰遜的計算機和Intractibility）：

任何計算問題可以表示爲圖靈機。

有可能將圖靈機作爲一個邏輯問題來表達，以滿足一定的複雜性約束。

因此，如果你能解決多項式時間的邏輯問題，你可以在多項式時間內解決圖靈機問題。

這（連同其他一些考慮）表明，如果你可以在多項式時間內解決邏輯問題，你可以在多項式時間內解決任何NP問題。這就是NP完全的定義，因此邏輯問題是NP完全的，可以用作其他問題的基礎。

使用的邏輯問題稱爲可滿足性（Satisfiability）（通常縮寫爲SAT）。給定一系列形式的條款（A或非B或非C）（由邏輯或命題連接的任意數量的命題和否定命題組成的條款）是否存在將命題的真值賦值給所有命題這些條款是真的嗎？

NP完整性是一個明確的屬性。你對於NP完全問題的懷疑的唯一原因是你認爲你可以減少另一個NP完全問題，但是還沒有設法找到一個方便的問題或者得到一個證明。

問題不在於是否存在NP完全問題，或者如何證明問題是NP完全的，但這意味着什麼。目前還沒有人提出一個多項式時間算法來解決一個NP完全問題，沒有人證明這種算法不可能存在。無論P = NP，我們當然沒有很好的算法來解決任何NP完全問題。

這是克萊浦基金會的千年問題之一，所以如果你能拿出一個證明，一些非常光明的人已經躲過了好幾年，那麼這裏有一百萬美元。