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