如果說，沒有一個NP完全問題有多項式時間演算法，那麼為什麼這個問題能被稱為NP完全問題？

因為，NP問題不就是能在多項式時間被NDTM所接受的語言？難道NP完全問題不屬於NP問題？求解答！！！

---

NP，NP-Complete，NP-hard是三個不同概念：

i) P

多項式時間內可以被確定型圖靈機求解的問題。

ii) NP

一般有兩個定義：

1. 多項式時間內可以被非確定型圖靈機求解的問題；

2. 多項式時間內可以通過確定型圖靈機驗證解的問題；

兩個定義目前認為等效，第二個定義用的比較多，第一個定義更為嚴格。需注意的是求解問題和對問題驗證解之間的區別。給定一個問題，求解通常難於驗證解。比如找出給定若干數中的最大者，驗證解難度和求解難度相當，都是O(N)；再比如排序，如果採用快速排序，驗證解仍然是O(N)，但是求解複雜度則是O(N*lgN)。

iii) NP-Complete

NP中所區分出來較為特殊的一類子問題。

NP中所有問題都可以在多項式時間內規約至某一子類問題，稱這一類子問題為NP-Complete。因此，NP-Complete是NP的一個子集。直覺上說，就是NP問題中最難的一類子問題。因為給定一個NP問題A，只要可以多項式時間內解決任意一個NP-Complete問題B，那麼就可以通過多項式的時間將A問題轉化為B問題進行求解，使得求解A問題仍具有多項式複雜度。

Cook定理說的就是SAT問題是NP-Complete問題，這也是第一個找到的NP-Complete具體問題。

通常情況下，證明一個具體問題A為NP-Complete，都要證明這個問題比某一個具體的NP-Complete問題更難，也就是經常說的多項式規約（也稱轉化）。即在多項式時間內將任意一個NP-Complete問題B規約為問題A。需要注意這裡規約的方向，是在多項式時間將B規約為A，而非將A規約為B。即證明，如果B可以求解，則可以通過多項式時間轉化，來間接求解A，因此A比B更難。

例如，根據Cook，如果證明A比SAT問題更難，即找到一個多項式時間內的規約方式將SAT轉化為A來求解，則證明A也是NP-Complete。但有趣的是，所有NP-Complete問題都是在多項式時間內可以相互規約的。即也存在一種規約方式，使得A問題在多項式時間內轉化為SAT問題進行求解。正是基於上述可以相互轉化的性質，所以將NP-Complete問題視為一類特殊子問題來對待，並從NP問題中獨立區分開來（類比集合論中A&<=B，B&<=A，則A=B）。這是一個邏輯上非常強的美麗結論。已知所找到的NP-Complete的問題，從最初的SAT問題已發展為現在成百上千個，廣泛存在於計算機的各個子領域中。

iv) NP-hard

不妨顧名思義的理解為，比NP問題更難的問題。

即，即使NP問題可以在多項式時間內解決，這一類問題仍然無法確保能在多項式時間內求解。

簡單來說，就是這類問題大家都普遍認為很難，但是卻又不知道具體有多難。

例如，給定某一問題C待求解。經過反覆嘗試，發現C非常難求解。只要找到一種辦法，將C問題轉化為某一熟悉的NP問題A，那麼就可以通過求解A來間接求解C。但問題在於，找不到（或者證明不存在）這樣的辦法，這時就稱C問題為NP-hard。

v) P vs NP

1. P&<=NP

多項式時間內確定型圖靈機可求解，因此自然也可在多項式時間內驗證解。

2. NP-Complete&

比如排序問題，屬於P，也屬於NP，但不屬於NP-Complete。

3. P？NP

關鍵在於P到底是否為NP的一個真子集。

根據上面的討論可知，如果能找到一個具體NP-Complete問題的多項式演算法，則可以證明P=NP。

因為所有NP-Complete問題相互等價，一個具體問題的多項式演算法可適用於所有其他NP-Complete問題。而NP-Complete問題又是NP問題中最難的一類，因此這樣一個具體演算法就可以在多項式時間內求解所有NP問題，從而P=NP。

因此，P？NP問題可以等價轉化為：對任意一個給定的NP-Complete問題，是否存在一個多項式演算法求解？若存在，則二者相等，反之亦反。

可以看到，P、NP、NP-Complete、NP-hard是計算複雜程度上逐漸遞增的幾個概念，而計算複雜度的最高表現形式則是不可計算性——即不是多項式還是指數級時間內可以計算的問題，而是根本無法計算，比如哥德爾不完備定理和與之等價的圖靈機停機問題。

希望有所幫助，歡迎討論。

---

瀉藥

沒看懂題主的邏輯。目前所謂的「演算法」都是確定性的，對應確定性圖靈機，怎麼扯到NDTM了。

揣測下題主的邏輯：

NP問題可以被非確定圖靈機在多項式時間接受 -&> 任一非確定圖靈機，存在確定性圖靈機接受相同的語言 -&> 存在確定性圖靈機在多項式時間接受該語言。

後一步邏輯是錯的。目前只知道如果語言L被非確定型圖靈機在多項式時間內接受，則一定存在多項式P使得語言L被時間複雜度為的確定型圖靈機程序所接受。所以P？NP沒有解決。

---

推薦閱讀：