這些概念以前老是犯糊涂，今天整清楚。
摘要:
P: Polynomial Solvable
NP: Non-determinstic Polynomial Solvable

0)詞語解釋：
Polynomial 【數】多項式的； 由平方，立方等常數次方或者更小的運算符和+,-,*,/等構成的式子及其這種式子的和
Non-deterministic: 非確定性的;
Turing-machine: 圖靈機; 英國數學家圖靈提出的計算模型, 一個兩端無限長的由小格子組成的帶子，每個格子可以存儲一個數，一個可以在帶子左右移動的游標或者指針或者不如叫磁頭(head), 磁頭可讀或修改格子里的數。 下面默認說的是確定性圖靈機，和非確定性圖靈機功能上等價
Algorithm: 算法。 給定一個問題的描述作為輸入，圖靈機求解的過程。 此過程有可能無限步長，則圖靈機永遠不會停止，除非被外部力量終止。
Polynomial algorithm: 多項式算法。 如果給定問題輸入的長度，常量n, 則如果圖靈機解答過程需要的是時間是以n為變量的多項式，則這個解法（也是個算法）是有多項式的時間復雜度的。
Decision question: 判定問題。 答案是yes或者no的問題

1) P問題和NP問題
P問題 (Polynomial Solvable)：如果一個判定問題是P問題，則這個問題存在一個多項式解法。 即圖靈機只需要多項式時間就可以得到答案, 既回答yes或者no。

NP問題(Nondeterminstic Polynomial Solvable)：如果一個判定問題是NP問題， 則這個問題的一個可能的解，可以在多項式時間內被驗證是否正確。 其實這不是本來的定義。 本來的定義是，NP問題是非確定性圖靈機有多項式解。但我們可以把非確定性圖靈機多項多可解轉化成確定性圖靈機多項式可驗證解。 確定性圖靈機更好好理解，所以用那個定義。

P問題是確定性圖靈機在多項式時間內求到解，NP問題是非確定性圖靈機在多項式時間內求到解，或者說NP問題是確定性圖靈機在多項式時間內驗證解.

所以NP問題比P問題更難。 就像前面有人說的，改卷的老師會驗證題目的答案是否正確，但他不一定會做這些題。

2) 關系
P 屬于 NP。 就是說，一個問題如果屬于P， 則一定屬于NP。 (這里P, NP表示符合定義的相關問題的集合)反過來則不一定，7大數學世紀難題之一就是問 P是否等于NP。

3) NPC 和 NP-hard
NPC, 即NP完全性問題。 任意一個NP問題都可規約到該問題，那么該問題稱為NP-complete（NPC）。 是指NP問題中的最難的問題。 即還沒有找到多項式解法，但多項式可驗證。 而且只要一個NPC問題有多項式解法，其它所有NP問題都會有一個多項式解法。

NP-hard是指所有還沒有找到多項式解法的問題, 并沒有限定屬于NP。 所以NP-hard比NPC范圍更大，也會更難。 NPC是NP-hard和NP的交集.。NPC問題都是NP-Hard問題。例如TSP優化問題、Hamilton問題不問題，它們不是NP問題，但是是NP-Hard問題。

總結

以上是生活随笔為你收集整理的关于P，NP，NPC和NP-hard的通俗解释的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。