整理一下。肯定有錯誤之處，請高手指正。

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

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

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

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

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

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

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