某此報告會上，提到NP問題，不是清楚，現查閱如下：
1）http://en.wikipedia.org/wiki/NP-hard上的解釋；
2）弄清楚這幾個概念：計算復雜性以及其排序和問題規約等；
##計算復雜性
這是描述一種算法需要多少“時間”的度量。（也有空間復雜性，但因為它們能相互轉換，所以通常我們就說時間復雜性。對于大小為 n 的輸入，我們用含 n 的簡化式子來表達。（所謂簡化式子，就是忽略系數、常數，僅保留最“大”的那部分）
比如找出 n 個數中最大的一個，很簡單，就是把第一個數和第二個比，其中大的那個再和第三個比，依次類推，總共要比 n-1 次，我們記作 O(n) (對于 n 可以是很大很大的情況下，-1可以忽略不計了）。
再比如從小到大排好的 n 個數，從中找出等于 x 的那個。一種方法是按著順序從頭到尾一個個找，最好情況是第一個就是 x，最壞情況是比較了 n 次直最后一個，因此最壞情況下的計算復雜度也是 O(n)。還有一種方法：先取中間那個數和 x 比較，如偏大則在前一半數中找，如偏小則在后一半數中找，每次都是取中間的那個數進行比較，則最壞情況是 lg(n)/lg2。忽略系數lg2，算法復雜度是O(lgn)。

##計算復雜性的排序：
根據含 n 的表達式隨 n 增大的增長速度，可以將它們排序：1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常數）< ... < 2^n。最后這個 2 的 n 次方就是級數增長了，讀過棋盤上放麥粒故事的人都知道這個增長速度有多快。而之前的那些都是 n 的多項式時間的復雜度。為什么我們在這里忽略所有的系數、常數，例如 2*n^3+9*n^2 可以被簡化為 n^3？用集合什么的都能解釋，我忘了精確的說法了。如果你還記得微積分的話就想像一下對 (2*n^3+9*n^2)/(n^3) 求導，結果是0，沒區別，對不？

##P 問題：對一個問題，凡是能找到計算復雜度可以表示為多項式的確定算法，這個問題就屬于 P (polynomial) 問題。

##NP 問題：
NP 中的 N 是指非確定的(non-deterministic）算法，這是這樣一種算法：（1）猜一個答案。（2）驗證這個答案是否正確。（3）只要存在某次驗證，答案是正確的，則該算法得解。
NP (non-deterministic polynomial)問題就是指，用這樣的非確定的算法，驗證步驟（2）有多項式時間的計算復雜度的算法。

##問題的歸約：
這……我該用什么術語來解釋呢？集合？太難說清了……如果你還記得函數的映射的話就比較容易想象了。
大致就是這樣：找從問題1的所有輸入到問題2的所有輸入的對應，如果相應的，也能有問題2的所有輸出到問題1的所有輸出的對應，則若我們找到了問題2的解法，就能通過輸入、輸出的對應關系，得到問題1的解法。由此我們說問題1可歸約到問題2。

##NP-Hard：
有這樣一種問題，所有 NP 問題都可以歸約到這種問題，我們稱之為 NP-hard 問題。

##NP完全問題 (NP-Complete)：
如果一個問題既是 NP 問題又是 NP-Hard 問題，則它是 NP-Complete 問題。可滿足性問題就是一個 NP 完全問題，此外著名的給圖染色、哈密爾頓環、背包、貨郎問題都是 NP 完全問題。

從直覺上說，P<=NP<=NP-Complete<=NP-Hard，問題的難度遞增。但目前只能證明 P 屬于 NP，究竟 P=NP 還是 P 真包含于 NP 還未知。