http://www.cs.pitt.edu/~ztliu/wordpress/2011/05/np-problem/
首先解釋一下什么是NP問題，什么是NP hard問題，什么是NP完全問題。
看下面的圖，他們之間的關(guān)系表示的比較清楚。
P Problem：這個(gè)應(yīng)該最易理解，就是一個(gè)問題可以在Polynominal的時(shí)間的得到解決，當(dāng)然，是對(duì)于任意input size。
NP Problem：對(duì)于一類問題，我們可能沒有一個(gè)已知的快速的方法得到問題的答案，但是如果給我們一個(gè)candidate answer，我們能夠在polynominal的時(shí)間內(nèi)驗(yàn)證這個(gè)candidate answer到底是不是我們已知問題的答案，這類問題叫做NP problem。所以很顯然 P Problem是NP problem的一個(gè)子集。
NP-hard Problem：對(duì)于這一類問題，用一句話概括他們的特征就是“at least as hard as the hardest problems in NP Problem”， 就是NP-hard問題至少和NP問題一樣難。
NP-complete Problem：對(duì)于這一類問題，他們滿足兩個(gè)性質(zhì)，一個(gè)就是在polynomial時(shí)間內(nèi)可以驗(yàn)證一個(gè)candidate answer是不是真正的解，另一個(gè)性質(zhì)就是我們可以把任何一個(gè)NP問題在polynomial的時(shí)間內(nèi)把他的input轉(zhuǎn)化，使之成為一個(gè)NP-complete問題。
所以對(duì)于NP-hard問題，我們可以把他們分成兩個(gè)部分，一部分可以用polynomial的時(shí)間驗(yàn)證一個(gè)candidate answer是不是真正的answer，這一部分問題組成了NP-complete集合。
我們經(jīng)常說的NP=P或者NP！=P，其實(shí)就是說目前而言，我們并不知道，是不是對(duì)于NP Problem集合里面的所有問題，都能夠在Polynomial的時(shí)間內(nèi)解決。當(dāng)然只里面比較interesting的一點(diǎn)是，如果我們能把NP-complete集合中的任意一個(gè)問題在polynomial的時(shí)間內(nèi)解決了，那么所有的NP問題都可以在polynomial的時(shí)間內(nèi)解決。原因，看看上面說的NP-complete的性質(zhì)就知道了，因?yàn)槿魏我粋€(gè)NP問題都可以在polynomial的時(shí)間內(nèi)把他的input轉(zhuǎn)化，使之成為一個(gè)NP-complete問題，所以….
介紹了上面說的一些定義，來舉幾個(gè)經(jīng)典的NP-complete的問題。
Vertex Cover http://en.wikipedia.org/wiki/Vertex_Cover
Informally來說，就是對(duì)于一個(gè)圖G(V,E)，我們?cè)赩中選一個(gè)subset V’， 使得E中的所有邊得兩點(diǎn)中的一個(gè)點(diǎn)在V’中。 所謂Vertex Cover也就是說V’中的點(diǎn)cover了每一條邊（因?yàn)槊恳粭l邊至少有一端是在V’中的啦）給你一個(gè)G(V,E)和一個(gè)k，問你在整個(gè)G中，是否存在一個(gè)大小為k的Vertex Cover（Decision Problem）
Formally, a vertex cover of a graph G is a set C of vertices such that each edge of G is incident to at least one vertex in C . The set C is said to cover the edges of G . The following figure shows examples of vertex covers in two graphs (the set C is marked with red).
3-CNF-SAT http://en.wikipedia.org/wiki/3SAT#3-satisfiability
舉個(gè)例子，
[latex]
E = (X_1 \lor \lnot X_2 \lor \lnot X_3) \wedge (X_1 \lor X_2 \lor X_4)
[/latex]
每一個(gè)括號(hào)包括的東西叫一個(gè)clause，里面的X1，X2，X3在離散數(shù)學(xué)里面叫做文字，取值True或者False。每個(gè)括號(hào)之間是合取，括號(hào)里面是析取，這個(gè)問題就是，對(duì)于這樣的一個(gè)表達(dá)式，是不是能找到一組Xi的值，使得表達(dá)式為True。Given the expression, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?
Integer Linear Programming http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns
當(dāng)然這個(gè)最顯而易見了，就是LP中的所有變量都要求是整數(shù)了。關(guān)于Linear Programming的問題，后面會(huì)專門有一篇文章來講解。O(∩_∩)O~
下面來看看我們經(jīng)常會(huì)遇到的一些證明問題。
證明一個(gè)問題是NP問題。證明給你一個(gè)結(jié)果，你能在polynomial的時(shí)間內(nèi)驗(yàn)證他的正確性
證明一個(gè)問題是NP-hard的。對(duì)于證明一個(gè)問題是NP-hard，我們經(jīng)常用到的一個(gè)technique是歸約（reduction），通常用<=這個(gè)符號(hào)來表示，如P<=Q，這個(gè)就表示 P is reducible to Q or Q is the reduction from P or P is reduced to Q. P問題可以歸約到Q問題。可以把P歸約到Q。 這里的reduction的符號(hào)可以當(dāng)成是 比較難易程度的小于等于號(hào)，意味著問題Q至少和問題P一樣難。當(dāng)我們要證明一個(gè)問題是NP-hard的時(shí)候，我們通常要做的是找到一個(gè)NPC問題（就用這個(gè)代替NP-complete問題），把這個(gè)NPC問題歸約到NP-hard上去，即NPC<=NP-hard。
證明一個(gè)問題是NPC的。要證NPC，我們要分兩步走，第一步證明這個(gè)問題屬于NP，就是驗(yàn)證答案（感覺這句話我都說爛了）。第二步，證明這個(gè)問題是NP-hard的。當(dāng)然這里面第二步是問題的關(guān)鍵，但是第一步也一定要在證明里面提到。
如何證明一個(gè)問題是NP-hard 是以上證明的關(guān)鍵，即如何歸約。
這里我們歸約要做的主要步驟就是，
1.把NPC的input轉(zhuǎn)化到NP-hard的input，即每一個(gè)NPC的input，實(shí)際上都是一個(gè)NP-hard的input。
2.把NP-hard的output轉(zhuǎn)化到NPC的output上來，說明給我一個(gè)NP-hard的output，我就能給你一個(gè)NPC的output。
注意：以上的兩個(gè)轉(zhuǎn)化都要在polynomial的時(shí)間內(nèi)完成。
下面舉幾個(gè)例子來證明上面的歸約的方法。
例 用3SAT 證明 Vertex Cover是NP-hard的。即 3SAT <= Vertex Cover
這個(gè)就是表明我們已知3SAT這個(gè)問題是NP-complete的，如何把3SAT問題歸約到Vertex Cover上。
首先，我們要建立我們的通過input建立這兩個(gè)問題的對(duì)應(yīng)。假設(shè)我的3SAT是
[latex]
E = (X_1 \lor \lnot X_2 \lor \lnot X_3) \wedge (X_1 \lor X_2 \lor X_4)
[/latex]
我們按照下面的方法構(gòu)造我們的Graph，對(duì)應(yīng)每一個(gè)個(gè)變量Xi，我們構(gòu)造點(diǎn) Xi和~Xi，對(duì)于每一個(gè)clause，我們構(gòu)造3個(gè)點(diǎn)，這3個(gè)點(diǎn)直接彼此有邊，假設(shè)這三個(gè)點(diǎn)叫A,B,C。同時(shí)我們還要建立A,B,C這三個(gè)點(diǎn)和該clause的聯(lián)系：假設(shè)我們的clause是 （X1 V ~X2 V ~X3） 我們就把X1和A連起來，~X2和B連起來，~X3和C連起來。注意，每一個(gè)clause有一個(gè)全連通的三角，他們共用那6個(gè)變量點(diǎn)（X1，~X1，X2，~X2，X3，~X3） 如下圖所示。
要注意的一點(diǎn)是，對(duì)于E中的每一個(gè)clause，我們都對(duì)應(yīng)圖里面的一個(gè)三角形（也就是我用矩形圈住的那部分），同時(shí)所有的clause共享上面的六個(gè)點(diǎn)，也就是2*變量個(gè)數(shù) 那么多個(gè)點(diǎn)是共用的。
通過這個(gè)圖，我們也就建立起了3SAT和Vertex Cover之間的聯(lián)系。通常這個(gè)也是此類證明問題中最難和最creative的部分。
后面就是表述一下如何進(jìn)行轉(zhuǎn)換的。通常這個(gè)是很trival的部分。
1）假設(shè)我有一個(gè)解能滿足3SAT，那么我就一定能找到相應(yīng)的解滿足Veterx Cover。 如上圖，3SAT滿足了，必然每一個(gè)clause滿足，就拿 (X1 V ~X2 V ~X3) 為例，這個(gè)式子滿足了，必有一個(gè)變量為true，它可以是X1或者~X2或者~X3，假設(shè)X1為true，這時(shí)對(duì)應(yīng)的vertex cover中，我們就選上面6個(gè)點(diǎn)中的X1，同時(shí)對(duì)于下面的三角形中的3個(gè)點(diǎn)，我們選除了那個(gè)與X1相連的另外兩個(gè)點(diǎn)。對(duì)于每一個(gè)clause，我們都可以這樣做，同時(shí)，我們也cover了這個(gè)圖中的所有邊。也就是我們有了一個(gè)滿足要求的vertex cover。
2）假設(shè)我有一個(gè)解能滿足Vertex Cover，那么我就一定能找到相應(yīng)的解滿足3SAT。因?yàn)橐猚over這個(gè)圖，所以三角形里面至少要cover兩個(gè)點(diǎn)，上面的一對(duì)一對(duì)的pair里面也至少要cover一個(gè)，所以對(duì)于一個(gè)size為n+2m的vertex cover（n是變量個(gè)數(shù)，m是clause的個(gè)數(shù)），我們一定可以找到一個(gè)滿足的3SAT，（顯然啊，因?yàn)槊總€(gè)clause都有一個(gè)點(diǎn)和上面的一對(duì)一對(duì)pair的點(diǎn)相連） （說的好拗口，郁悶。還不清楚的可以看下這個(gè)鏈接 http://users.eecs.northwestern.edu/~fortnow/classes/w08/EECS395/lecture11.pdf ）
然后，然后，。。。我們就證完了。
例 用3SAT證明ILP是NP-hard的。即 3SAT <= ILP
還是首先找映射，這個(gè)映射不涉及圖的東西，應(yīng)該比較容易構(gòu)造和理解。
還是拿上面那個(gè)3SAT的例子說事。對(duì)于 每個(gè)clause，我們都對(duì)應(yīng)于ILP中的一個(gè)constraint，比如 E中有4個(gè)變量，X1，X2，X3 和X4， 我們的ILP中也有同樣的這4個(gè)變量，并且我們要求他們都是只能取0 或 1。對(duì)于一個(gè)clause，如(X1 V ~X2 V ~X3) ，我們對(duì)應(yīng)的constraint是 “X1 + （1-X2）+（1-X3）>=1”，很顯然了，ILP中的變量選0對(duì)應(yīng)于3SAT中的變量選false，ILP中的變量選1對(duì)應(yīng)于3SAT中的變量選true，這樣我們就映射好了。
很顯然，這兩個(gè)問題的input/output的轉(zhuǎn)換trival的不行了。如果一個(gè)clause滿足了，對(duì)應(yīng)的那個(gè)ILP中的constraint肯定也滿足了；反之依然。偷個(gè)懶~O(∩_∩)O~
證畢。
這類NP的證明問題其實(shí)還是很有難度的，只能說很鍛煉腦子，對(duì)于它有沒有用，這要看你對(duì)“useful”的定義了，仁者見仁，智者見智吧。
先來看一個(gè)小故事：（轉(zhuǎn)自： http://zhm2k.blog.163.com/blog/static/5981506820095233143571/ ）
假如老板要你解決一個(gè)問題，你絞盡腦汁還是想不出來，叫天天不應(yīng)，叫地地不靈，這時(shí)你走進(jìn)老板辦公室，可以采取3種策略：
1）圖1：
一副倒霉像，神情猥瑣，可憐巴巴的說：老板，我沒做出來，我想我是太蠢了……
boss：蠢材！滾！
(失敗……)
2）圖2：
雄赳赳氣昂昂跨進(jìn)老板辦公室，大吼一聲：小樣，你丫給我問題根本就無解，害我白想這么些天，我靠！
boss：我才靠，自己做不出來就說這個(gè)問題無解，要是人人都這樣混，我這老板還當(dāng)個(gè)屁阿，滾！
(做不出來還如此氣概，不僅失敗，而且欠扁……)
3）圖3：
從容不迫的說：老板，我做不出來，但是，我敢肯定，那些大牛們也照樣做不出來。
boss：原來是這樣，那也難為你了。
以上三副圖雖然是一個(gè)笑話，但也可以為我們的生活研究提供一些思路和指導(dǎo)。當(dāng)你面對(duì)一個(gè)問題解決不了時(shí)，那么就試圖去證明別人也解決不了，這的確是一個(gè)偷懶逃避的好借口。我覺得P、NP、NP-complete、NP-hard這些名稱的出現(xiàn)，就是因?yàn)槟承╇y問題，連大牛們都解決不了，無可奈何之下，只好定義一堆東西，為自己找個(gè)理由，免得說自己太笨了。其實(shí)這是給出一個(gè)面對(duì)難解問題的解決思路，如果無法得到最優(yōu)解，那么先去嘗試驗(yàn)證哪些解是不是最優(yōu)解。
下面依次介紹 ：
一、計(jì)算復(fù)雜性
計(jì)算復(fù)雜性一般包括時(shí)間復(fù)雜度和空間復(fù)雜度，時(shí)間復(fù)雜度并不是某算法實(shí)際運(yùn)行需要的時(shí)間，而是漸進(jìn)時(shí)間復(fù)雜度，即當(dāng)問題規(guī)模趨向于無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。常見的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n^2)、立方階O(n^3)、k次方階O(n^k)、指數(shù)階O(2^n)。這里用大O表示法來表述，給出的是算法的最壞情況的時(shí)間代價(jià)。
復(fù)雜度關(guān)系：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!
其中c是一個(gè)常量，如果一個(gè)算法的復(fù)雜度為c 、 log2N 、n 、 n*log2N ，那么這個(gè)算法時(shí)間效率比較高，叫做多項(xiàng)式級(jí)的復(fù)雜度。如果是 2^n , 3^n ,n!，那么稍微大一些的n就會(huì)令這個(gè)算法不能動(dòng)了，這些是非多項(xiàng)式級(jí)的，其復(fù)雜度計(jì)算機(jī)往往不能承受。當(dāng)我們?cè)诮鉀Q一個(gè)問題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。
空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。這里不 再細(xì) 講。
自然地，人們會(huì)想到一個(gè)問題：會(huì)不會(huì)所有的問題都可以找到復(fù)雜度為多項(xiàng)式級(jí)的算法呢？很遺憾，答案是否定的。有些問題甚至根本不可能找到一個(gè)正確的算法來，這稱之為“不可解問題”(Undecidable Decision Problem)。
二、P問題（Polynomial Solvable）
定義：那些可以在多項(xiàng)式( polynomial )時(shí)間內(nèi)解決的問題，稱為P問題。（或：如果一個(gè)問題可以找到一個(gè)能在多項(xiàng)式的時(shí)間里解決它的算法，那么這個(gè)問題就屬于P問題。）
時(shí)間復(fù)雜度如(n^2, n^4, n(log(n)))都是多項(xiàng)式時(shí)間的，指數(shù)級(jí)別的如(2^n，n^n)這些就不是多項(xiàng)式時(shí)間了。
三、NP問題（Non-determinstic Polynomial Solvable）
定義：給定一個(gè)解，我們可以在多項(xiàng)式時(shí)間內(nèi)檢查他正確與否的決策問題，為NP問題。
比如，我要找一個(gè)圖的哈密頓路徑，隨便給我一個(gè)解，我都可以在多項(xiàng)式時(shí)間內(nèi)檢查它是不是哈密頓路徑。只要形如定義的問題，就是NP問題。
之所以要定義NP問題，是因?yàn)橥ǔＶ挥蠳P問題才可能找到多項(xiàng)式的算法。我們不會(huì)指望一個(gè)連多項(xiàng)式地驗(yàn)證一個(gè)解都不行的問題存在一個(gè)解決它的多項(xiàng)式級(jí)的算法。相信讀者很快明白，信息學(xué)中的號(hào)稱最困難的問題——“NP問題”，實(shí)際上是在探討NP問題與P類問題的關(guān)系。
很顯然，所有的P類問題都是NP問題。也就是說，能多項(xiàng)式地解決一個(gè)問題，必然能多項(xiàng)式地驗(yàn)證一個(gè)問題的解——既然正解都出來了，驗(yàn)證任意給定的解也只需要比較一下就可以了。關(guān)鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點(diǎn)來說明。如果把所有P類問題歸為一個(gè)集合P中，把所有 NP問題劃進(jìn)另一個(gè)集合NP中，那么，顯然有P屬于NP。現(xiàn)在，所有對(duì)NP問題的研究都集中在一個(gè)問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實(shí)就一句話：證明或推翻P=NP。
目前為止這個(gè)問題還“啃不動(dòng)”。但是，一個(gè)總的趨勢(shì)、一個(gè)大方向是有的。人們普遍認(rèn)為，P=NP不成立，也就是說，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式級(jí)復(fù)雜度的算法的NP問題。人們?nèi)绱藞?jiān)信P≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-complete問題，也即所謂的NPC問題。
四、歸約
為了說明NPC問題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)。
簡(jiǎn)單地說，一個(gè)問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。
“問題A可約化為問題B”有一個(gè)重要的直觀意義：B的時(shí)間復(fù)雜度高于或者等于A的時(shí)間復(fù)雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時(shí)間復(fù)雜度比A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。
從約化的定義中我們看到，一個(gè)問題約化為另一個(gè)問題，時(shí)間復(fù)雜度增加了，問題的應(yīng)用范圍也增大了。通過對(duì)某些問題的不斷約化，我們能夠不斷尋找復(fù)雜度更高，但應(yīng)用范圍更廣的算法來代替復(fù)雜度雖然低，但只能用于很小的一類問題的算法。再回想前面講的P和NP問題，聯(lián)想起約化的傳遞性，自然地，我們會(huì)想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個(gè)稍復(fù)雜的大NP問題，那么最后是否有可能找到一個(gè)時(shí)間復(fù)雜度最高，并且能“通吃”所有的 NP問題的這樣一個(gè)超級(jí)NP問題？答案居然是肯定的。也就是說，存在這樣一個(gè)NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個(gè)問題，那么所有的NP問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個(gè)，它有很多個(gè)，它是一類問題。這一類問題就是傳說中的NPC 問題，也就是NP-完全問題。
五、NP-complete問題
定義：NP-c問題是這樣的一類問題，首先他是屬于NP的，而且他是NP問題里面最難解決的問題。難到什么程度？只要其中某個(gè)問題可以在P時(shí)間內(nèi)解決，那么所有的NP問題就都可以在P時(shí)間內(nèi)解決了。
既然所有的NP問題都能約化成NPC問題，那么只要任意一個(gè)NPC問題找到了一個(gè)多項(xiàng)式的算法，那么所有的NP問題都能用這個(gè)算法解決了，NP也就等于P 了。因此，給NPC找一個(gè)多項(xiàng)式算法太不可思議了。
“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。
NP-c問題的定義出來了，但是，它忽悠了半天，除了說明這類問題比較難之外，其他啥也沒有。我們還是不知道到底什么問題是NP-c問題，如何判定一個(gè)問題是不是NP-c問題。
1970年，cook同志發(fā)明了cook定理，找到了第一個(gè)NP-c問題，SAT(Satisfiability)問題（邏輯電路問題）。他是這么說的，如果SAT問題可以在P時(shí)間解決，那么所有的NP問題都可以在P時(shí)間內(nèi)解決。
有了第一個(gè)NPC問題后，一大堆NPC問題就出現(xiàn)了，因?yàn)樵僮C明一個(gè)新的NPC問題只需要將一個(gè)已知的NPC問題約化到它就行了。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題，其他還有圖染色問題、背包問題等。現(xiàn)在被證明是NPC問題的有很多，任何一個(gè)找到了多項(xiàng)式算法的話所有的NP問題都可以完美解決了。因此說，正是因?yàn)镹PC問題的存在，P=NP變得難以置信。
六、NP-hard問題
定義：NP-hard問題是這樣的問題，只要其中某個(gè)問題可以在P時(shí)間內(nèi)解決，那么所有的NP問題就都可以在P時(shí)間內(nèi)解決了。NP-c問題就是NP-hard問題。但注意NP-hard問題它不一定是NP問題，比如，下圍棋就是NP-hard問題，但不是NP問題，我們要在一個(gè)殘局上找一個(gè)必勝下法，告訴我們下一步下在哪里。顯然，我們找不這個(gè)解，而且更難的是，就算有人給我了一個(gè)解，我們也無法在P時(shí)間內(nèi)判斷它是不是正確的。
更詳細(xì)的 ，以下轉(zhuǎn)自： http://blog.csdn.net/crfoxzl/article/details/2192957
NP問題 就是指其解的正確性可以在多項(xiàng)式時(shí)間內(nèi)被檢查的一類問題。 比如說數(shù)組求和，得到一個(gè)解，這個(gè)解對(duì)不對(duì)呢，顯然是可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證的。再比如說SAT，如果得到一個(gè)解，也是能在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證正確性的。所以SAT和求和等等都是NP問題。然后呢， 有一部分NP問題的解已經(jīng)可以在多項(xiàng)式時(shí)間內(nèi)找到，比如數(shù)組求和，這部分問題就是NP中比較簡(jiǎn)單的一部分，被命名為P類問題。 那么P以外的NP問題，就是目前還不能夠在多項(xiàng)式時(shí)間內(nèi)求解的問題了。會(huì)不會(huì)將來某一天，有大牛發(fā)明了牛算法，把這些問題都在多項(xiàng)式時(shí)間內(nèi)解決呢？也就是說，會(huì)不會(huì)所有的NP問題，其實(shí)都是P類問題呢，只是人類尚未發(fā)現(xiàn)呢？NP=P嗎？
可想而知，證明NP=P的路途是艱難的，因?yàn)镹P問題實(shí)在太多了，要一一找到多項(xiàng)式算法。這時(shí) Stephen A. Cook 這位大牛出現(xiàn)了，寫了一篇 The Complexity of Theorem Proving Procedures ，提出了一個(gè)NP-complete的概念。 NPC指的是NP問題中最難的一部分問題，所有的NP問題都能在多項(xiàng)式時(shí)間內(nèi)歸約到NPC上。 所謂 歸約 是指，若A歸約到B，B很容易解決，則A很容易解決。顯然， 如果有任何一道NPC問題在多項(xiàng)式時(shí)間內(nèi)解決了，那么所有的NP問題就都成了P類問題 ，NP=P就得到證明了，這極大的簡(jiǎn)化了證明過程。那么怎樣證明一個(gè)問題C是NP完全問題呢？首先，要證明C是NP問題，也就是C的解的正確性容易驗(yàn)證；然后要證明有一個(gè)NP完全問題B，能夠在多項(xiàng)式時(shí)間內(nèi)歸約到C。這就要求必須先存在至少一個(gè)NPC問題。 這時(shí)Cook大牛就在1971年證明了NP完全問題的祖先就是 SAT 。SAT問題是指給定一個(gè)包含n個(gè)布爾變量的邏輯式，問是否存在一個(gè)取值組合，使得該式被滿足。Cook證明了SAT是一個(gè)NPC問題，如果SAT容易解決，那么所有NP都容易解決。Cook是怎樣做到的呢？
他通過 非確定性圖靈機(jī) 做到的。 非確定性圖靈機(jī)是一類特殊的圖靈機(jī)，這種機(jī)器很會(huì)猜，只要問題有一個(gè)解，它就能夠在多項(xiàng)式時(shí)間內(nèi)猜到。 Cook證明了，SAT總結(jié)了該機(jī)器在計(jì)算過程中必須滿足的所有約束條件，任何一個(gè)NP問題在這種機(jī)器上的計(jì)算過程，都可以描述成一個(gè)SAT問題。所以，如果你能有一個(gè)解決SAT的好算法，你就能夠解決非確定性圖靈機(jī)的計(jì)算問題，因?yàn)镹P問題在非圖機(jī)上都是多項(xiàng)式解決的，所以你解決了SAT，就能解決所有NP， 因此——SAT是一個(gè)NP完全問題。 感謝Cook，我們已經(jīng)有了一個(gè)NPC問題，剩下的就好辦了，用歸約來證明就可以了。目前人們已經(jīng)發(fā)現(xiàn)了 成千上萬的NPC問題 ，解決一個(gè)，NP=P就得證，可以得 千年大獎(jiǎng) （我認(rèn)為還能立刻獲得圖靈獎(jiǎng)）。
那么肯定有人要問了，那么NP之外，還有一些連驗(yàn)證解都不能多項(xiàng)式解決的問題呢。這部分問題，就算是NP=P，都不一定能多項(xiàng)式解決，被命名為NP-hard問題。NP-hard太難了，怎樣找到一個(gè)完美的女朋友就是NP-hard問題。一個(gè)NP-hard問題，可以被一個(gè)NP完全問題歸約到，也就是說，如果有一個(gè)NP-hard得到解決，那么所有NP也就都得到解決了。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
