某此報(bào)告會(huì)上，提到NP問(wèn)題，不是清楚，現(xiàn)查閱如下：
1）
http://en.wikipedia.org/wiki/NP-hard上的解釋；
2）弄清楚這幾個(gè)概念：計(jì)算復(fù)雜性以及其排序和問(wèn)題規(guī)約等；
##計(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è)比，依次類推，總共要比 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)。
##計(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ò)棋盤上放麥粒故事的人都知道這個(gè)增長(zhǎng)速度有多快。而之前的那些都是 n 的多項(xiàng)式時(shí)間的復(fù)雜度。為什么我們?cè)谶@里忽略所有的系數(shù)、常數(shù)，例如 2*n^3+9*n^2 可以被簡(jiǎn)化為 n^3？用集合什么的都能解釋，我忘了精確的說(shuō)法了。如果你還記得微積分的話就想像一下對(duì) (2*n^3+9*n^2)/(n^3) 求導(dǎo)，結(jié)果是0，沒(méi)區(qū)別，對(duì)不？
##P 問(wèn)題：對(duì)一個(gè)問(wèn)題，凡是能找到計(jì)算復(fù)雜度可以表示為多項(xiàng)式的確定算法，這個(gè)問(wèn)題就屬于 P (polynomial) 問(wèn)題。
##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ù)雜度的算法。
##問(wèn)題的歸約：
這……我該用什么術(shù)語(yǔ)來(lái)解釋呢？集合？太難說(shuō)清了……如果你還記得函數(shù)的映射的話就比較容易想象了。
大致就是這樣：找從問(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。
##NP-Hard：
有這樣一種問(wèn)題，所有 NP 問(wèn)題都可以歸約到這種問(wèn)題，我們稱之為 NP-hard 問(wèn)題。
##NP完全問(wèn)題 (NP-Complete)：
如果一個(gè)問(wèn)題既是 NP 問(wèn)題又是 NP-Hard 問(wèn)題，則它是 NP-Complete 問(wèn)題?？蓾M足性問(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 還未知。