整理一下。肯定有錯(cuò)誤之處，請(qǐng)高手指正。

NP問(wèn)題就是指其解的正確性可以在多項(xiàng)式時(shí)間內(nèi)被檢查的一類(lèi)問(wèn)題。比如說(shuō)數(shù)組求和，得到一個(gè)解，這個(gè)解對(duì)不對(duì)呢，顯然是可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的。再比如說(shuō)SAT，如果得到一個(gè)解，也是能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證正確性的。所以SAT和求和等等都是NP問(wèn)題。然后呢，有一部分NP問(wèn)題的解已經(jīng)可以在多項(xiàng)式時(shí)間內(nèi)找到，比如數(shù)組求和，這部分問(wèn)題就是NP中比較簡(jiǎn)單的一部分，被命名為P類(lèi)問(wèn)題。那么P以外的NP問(wèn)題，就是目前還不能夠在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題了。會(huì)不會(huì)將來(lái)某一天，有大牛發(fā)明了牛算法，把這些問(wèn)題都在多項(xiàng)式時(shí)間內(nèi)解決呢？也就是說(shuō)，會(huì)不會(huì)所有的NP問(wèn)題，其實(shí)都是P類(lèi)問(wèn)題呢，只是人類(lèi)尚未發(fā)現(xiàn)呢？NP=P嗎？

可想而知，證明NP=P的路途是艱難的，因?yàn)镹P問(wèn)題實(shí)在太多了，要一一找到多項(xiàng)式算法。這時(shí)Stephen A. Cook這位大牛出現(xiàn)了，寫(xiě)了一篇The Complexity of Theorem Proving Procedures，提出了一個(gè)NP-complete的概念。NPC指的是NP問(wèn)題中最難的一部分問(wèn)題，所有的NP問(wèn)題都能在多項(xiàng)式時(shí)間內(nèi)歸約到NPC上。所謂歸約是指，若A歸約到B，B很容易解決，則A很容易解決。顯然，如果有任何一道NPC問(wèn)題在多項(xiàng)式時(shí)間內(nèi)解決了，那么所有的NP問(wèn)題就都成了P類(lèi)問(wèn)題，NP=P就得到證明了，這極大的簡(jiǎn)化了證明過(guò)程。那么怎樣證明一個(gè)問(wèn)題C是NP完全問(wèn)題呢？首先，要證明C是NP問(wèn)題，也就是C的解的正確性容易驗(yàn)證；然后要證明有一個(gè)NP完全問(wèn)題B，能夠在多項(xiàng)式時(shí)間內(nèi)歸約到C。這就要求必須先存在至少一個(gè)NPC問(wèn)題。這時(shí)Cook大牛就在1971年證明了NP完全問(wèn)題的祖先就是SAT。SAT問(wèn)題是指給定一個(gè)包含n個(gè)布爾變量的邏輯式，問(wèn)是否存在一個(gè)取值組合，使得該式被滿(mǎn)足。Cook證明了SAT是一個(gè)NPC問(wèn)題，如果SAT容易解決，那么所有NP都容易解決。Cook是怎樣做到的呢？

他通過(guò)非確定性圖靈機(jī)做到的。非確定性圖靈機(jī)是一類(lèi)特殊的圖靈機(jī)，這種機(jī)器很會(huì)猜，只要問(wèn)題有一個(gè)解，它就能夠在多項(xiàng)式時(shí)間內(nèi)猜到。Cook證明了，SAT總結(jié)了該機(jī)器在計(jì)算過(guò)程中必須滿(mǎn)足的所有約束條件，任何一個(gè)NP問(wèn)題在這種機(jī)器上的計(jì)算過(guò)程，都可以描述成一個(gè)SAT問(wèn)題。所以，如果你能有一個(gè)解決SAT的好算法，你就能夠解決非確定性圖靈機(jī)的計(jì)算問(wèn)題，因?yàn)镹P問(wèn)題在非圖機(jī)上都是多項(xiàng)式解決的，所以你解決了SAT，就能解決所有NP，因此——SAT是一個(gè)NP完全問(wèn)題。感謝Cook，我們已經(jīng)有了一個(gè)NPC問(wèn)題，剩下的就好辦了，用歸約來(lái)證明就可以了。目前人們已經(jīng)發(fā)現(xiàn)了成千上萬(wàn)的NPC問(wèn)題，解決一個(gè)，NP=P就得證，可以得千年大獎(jiǎng)（我認(rèn)為還能立刻獲得圖靈獎(jiǎng)）。

那么肯定有人要問(wèn)了，那么NP之外，還有一些連驗(yàn)證解都不能多項(xiàng)式解決的問(wèn)題呢。這部分問(wèn)題，就算是NP=P，都不一定能多項(xiàng)式解決，被命名為NP-hard問(wèn)題。NP-hard太難了，怎樣找到一個(gè)完美的女朋友就是NP-hard問(wèn)題。一個(gè)NP-hard問(wèn)題，可以被一個(gè)NP完全問(wèn)題歸約到，也就是說(shuō)，如果有一個(gè)NP-hard得到解決，那么所有NP也就都得到解決了。 

 NP-Hard和NP-Complete 區(qū)別

對(duì)NP-Hard問(wèn)題和NP-Complete問(wèn)題的一個(gè)直觀(guān)的理解就是指那些很難（很可能是不可能）找到多項(xiàng)式時(shí)間算法的問(wèn)題. 因此一般初學(xué)算法的人都會(huì)問(wèn)這樣一個(gè)問(wèn)題: NP-Hard和NP-Complete有什么不同? 簡(jiǎn)單的回答是根據(jù)定義, 如果所有NP問(wèn)題都可以多項(xiàng)式歸約到問(wèn)題A, 那么問(wèn)題A就是NP-Hard; 如果問(wèn)題A既是NP-Hard又是NP, 那么它就是NP-Complete. 從定義我們很容易看出, NP-Hard問(wèn)題類(lèi)包含了NP-Complete類(lèi). 但進(jìn)一步的我們會(huì)問(wèn), 是否有屬于NP-Hard但不屬于NP-Complete的問(wèn)題呢? 答案是肯定的. 例如停機(jī)問(wèn)題, 也即給出一個(gè)程序和輸入, 判定它的運(yùn)行是否會(huì)終止. 停機(jī)問(wèn)題是不可判的, 那它當(dāng)然也不是NP問(wèn)題. 但對(duì)于SAT這樣的NP-Complete問(wèn)題, 卻可以多項(xiàng)式歸約到停機(jī)問(wèn)題. 因?yàn)槲覀兛梢詷?gòu)造程序A, 該程序?qū)斎氲墓礁F舉其變量的所有賦值, 如果存在賦值使其為真, 則停機(jī), 否則進(jìn)入無(wú)限循環(huán). 這樣, 判斷公式是否可滿(mǎn)足便轉(zhuǎn)化為判斷以公式為輸入的程序A是否停機(jī). 所以, 停機(jī)問(wèn)題是NP-Hard而不是NP-Complete.

 讓我冒著出錯(cuò)被人砸版磚的危險(xiǎn)來(lái)解釋一下P/NP/NP-Complete/NP-Hard。
　　
　　1，計(jì)算復(fù)雜性
　　這是描述一種算法需要多少“時(shí)間”的度量。（也有空間復(fù)雜性，但因?yàn)樗鼈兡芟嗷マD(zhuǎn)換，所以通常我們就說(shuō)時(shí)間復(fù)雜性。對(duì)于大小為 n 的輸入，我們用含 n 的簡(jiǎn)化式子來(lái)表達(dá)。（所謂簡(jiǎn)化式子，就是忽略系數(shù)、常數(shù)，僅保留最“大”的那部分）
　　比如找出 n 個(gè)數(shù)中最大的一個(gè)，很簡(jiǎn)單，就是把第一個(gè)數(shù)和第二個(gè)比，其中大的那個(gè)再和第三個(gè)比，依次類(lèi)推，總共要比 n-1 次，我們記作 O(n) (對(duì)于 n 可以是很大很大的情況下，-1可以忽略不計(jì)了）。
　　再比如從小到大排好的 n 個(gè)數(shù)，從中找出等于 x 的那個(gè)。一種方法是按著順序從頭到尾一個(gè)個(gè)找，最好情況是第一個(gè)就是 x，最壞情況是比較了 n 次直最后一個(gè)，因此最壞情況下的計(jì)算復(fù)雜度也是 O(n)。還有一種方法：先取中間那個(gè)數(shù)和 x 比較，如偏大則在前一半數(shù)中找，如偏小則在后一半數(shù)中找，每次都是取中間的那個(gè)數(shù)進(jìn)行比較，則最壞情況是 lg(n)/lg2。忽略系數(shù)lg2，算法復(fù)雜度是O(lgn)。
　　
　　2，計(jì)算復(fù)雜性的排序：
　　根據(jù)含 n 的表達(dá)式隨 n 增大的增長(zhǎng)速度，可以將它們排序：1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常數(shù)）< ... < 2^n。最后這個(gè) 2 的 n 次方就是級(jí)數(shù)增長(zhǎng)了，讀過(guò)棋盤(pán)上放麥粒故事的人都知道這個(gè)增長(zhǎng)速度有多快。而之前的那些都是 n 的多項(xiàng)式時(shí)間的復(fù)雜度。為什么我們?cè)谶@里忽略所有的系數(shù)、常數(shù)，例如 2*n^3+9*n^2 可以被簡(jiǎn)化為 n^3？用集合什么的都能解釋?zhuān)彝司_的說(shuō)法了。如果你還記得微積分的話(huà)就想像一下對(duì) (2*n^3+9*n^2)/(n^3) 求導(dǎo)，結(jié)果是0，沒(méi)區(qū)別，對(duì)不？
　　
　　2，P 問(wèn)題：對(duì)一個(gè)問(wèn)題，凡是能找到計(jì)算復(fù)雜度可以表示為多項(xiàng)式的確定算法，這個(gè)問(wèn)題就屬于 P (polynomial) 問(wèn)題。
　　
　　3，NP 問(wèn)題：
　　NP 中的 N 是指非確定的(non-deterministic）算法，這是這樣一種算法：（1）猜一個(gè)答案。（2）驗(yàn)證這個(gè)答案是否正確。（3）只要存在某次驗(yàn)證，答案是正確的，則該算法得解。
　　NP (non-deterministic polynomial)問(wèn)題就是指，用這樣的非確定的算法，驗(yàn)證步驟（2）有多項(xiàng)式時(shí)間的計(jì)算復(fù)雜度的算法。
　　
　　4，問(wèn)題的歸約：
　　這……我該用什么術(shù)語(yǔ)來(lái)解釋呢？集合？太難說(shuō)清了……如果你還記得函數(shù)的映射的話(huà)就比較容易想象了。
　　大致就是這樣：找從問(wèn)題1的所有輸入到問(wèn)題2的所有輸入的對(duì)應(yīng)，如果相應(yīng)的，也能有問(wèn)題2的所有輸出到問(wèn)題1的所有輸出的對(duì)應(yīng)，則若我們找到了問(wèn)題2的解法，就能通過(guò)輸入、輸出的對(duì)應(yīng)關(guān)系，得到問(wèn)題1的解法。由此我們說(shuō)問(wèn)題1可歸約到問(wèn)題2。
　　
　　5，NP-Hard：
　　有這樣一種問(wèn)題，所有 NP 問(wèn)題都可以歸約到這種問(wèn)題，我們稱(chēng)之為 NP-hard 問(wèn)題。
　　
　　6，NP完全問(wèn)題 (NP-Complete)：
　　如果一個(gè)問(wèn)題既是 NP 問(wèn)題又是 NP-Hard 問(wèn)題，則它是 NP-Complete 問(wèn)題?？蓾M(mǎn)足性問(wèn)題就是一個(gè) NP 完全問(wèn)題，此外著名的給圖染色、哈密爾頓環(huán)、背包、貨郎問(wèn)題都是 NP 完全問(wèn)題。
　　
　　從直覺(jué)上說(shuō)，P<=NP<=NP-Complete<=NP-Hard，問(wèn)題的難度遞增。但目前只能證明 P 屬于 NP，究竟 P=NP 還是 P 真包含于 NP 還未知。