原文地址： /csshuke/article/details/74909562
希望通過這篇文章可以不僅讓計算機相關專業的人可以看懂和區分什麽是P類問題什麽是NP類問題，更希望達到的效果是非專業人士比如學文科的朋友也可以有壹定程度的理解。
有壹則程序員界的笑話，就是有壹哥們去google面試的時候被問到壹個問題是：在什麽情況下P=NP，然後他的回答是”當N=1的時候”。這是我第壹次聽說P=NP問題，大概是在臨近畢業為找工作而準備的時候。
這幾天科技類新聞的頭條都被阿爾法狗大戰李世石刷爆了，雖然我也不是AI專家，但是也想從普通人的角度來寫點東西來聊聊這個有意思的事情，在搜集資料的時候又壹次看到了NP問題，於是想開個小差，在寫下壹篇文章《AI是怎麽下圍棋的?》之前，先說說這個NP問題哈。
最簡單的定義是這樣的：
P問題：
壹個問題可以在多項式（ ）的時間復雜度內解決。
NP問題：
壹個問題的解可以在多項式的時間內被驗證。
NP-hard問題：
任意np問題都可以在多項式時間內歸約為該問題，但該問題本身不壹定是NP問題。歸約的意思是為了解決問題A，先將問題A歸約為另壹個問題B，解決問題B同時也間接解決了問題A。
NPC問題：
既是NP問題，也是NP-hard問題。
這樣的定義雖然簡單，但是對於第壹次接觸P、NP的人來說，就像前壹陣問妳什麽是“引力波”而妳回答：引力波是時空的漣漪。從答案中幾乎沒有得到任何有意義的理解。所以接來來的內容希望不僅計算機相關專業的人可以看懂，希望達到的效果是文科生們也可以有壹定程度的理解。
現階段雖然電腦已經非常的普及，有人用它來上網，有用它來的遊戲，有用它來看片，但是很少人有還在乎電腦的本質是計算機，它在給人們的日常生活帶來娛樂和方便的同時表現的其實是其龐大的計算能力。日常生活中我們使用的各種五花八門的軟件，其實都是壹組計算機程序，而程序則可以看作是壹系列算法，而我們看到的計算機的硬件的作用就是處理這些算法。這裏的所說算法不只是簡單的加減乘除，而是包括下面這些要素：
算術運算：加減乘除等運算
邏輯運算：或、且、非等運算
關系運算：大於、小於、等於、不等於等運算
數據傳輸：輸入、輸出、賦值等運算
以及通過控制結構來控制處理這些運算或操作的順序。說到這裏有點擔心有些朋友已經不是很明白了，舉個例子吧。
我們如何從n個數裏面挑出最大的數。這個簡單吧，就只需要壹個壹個數的對比過去就行了。具體說也就是先比較n和n-1，記下比較大的那個數，接著我們再比較記下的這個數和n-2，又記下比較大的數，這樣壹直比到最後壹個數。這整個比較的過程我們就可以把其叫作算法，而這個算法就包含了上述的這些要素。給我們的n個數就是算法的輸入數據，我們要挑選出最大的那個數就是算法的輸出數據，當中我們判斷大小的時候必然采用了壹些基礎的算術運算或關系運算。
希望說到這裏大家能夠基本理解什麽是算法，因為接下來我要花壹點時間說說什麽是算法的時間復雜度。要計算或解決壹個問題，該問題通常有壹個大小規模，用n表示。我們還是引用上面的例子，從n個數裏面找出最大的那個數，這個n就是該問題的規模大小。怎麽找呢？我們要通過比較n-1次才能得到結果，這個n-1次就可以理解為所花的時間，也就是時間復雜度。再比如，將這n個數按從大至小排序，n是其規模大小，若是我們按照這樣的方法：第壹次從n個數裏找最大，第二次從n-1個數裏找最大，以此類推，需要的比較次數就是n(n-1)/2。我們所用的方法稱之庫為算法，那麽n(n-1)/2就是該算法的時間復雜度。對於時間復雜度，當n足夠大時，我們只註重最高次方的那壹項，其他各項可以忽略，另外，其常數系數也不重要，所以，n(n-1)/2我們只重視n的平方這壹項了，記為 ，這就是該算法對該問題的時間復雜度的專業表示。
時間復雜度其實並不是表示壹個程序解決問題具體需要花多少時間，而是當問題規模擴大後，程序需要的時間長度增長得有多快。也就是說，對於高速處理數據的計算機來說，處理某壹個特定數據的效率不能衡量壹個程序的好壞，而應該看當這個數據的規模變大到數百倍後，程序運行時間是否還是壹樣，或者也跟著慢了數百倍，或者變慢了數萬倍。不管數據有多大，程序處理花的時間始終是那麽多的，我們就說這個程序很好，具有 的時間復雜度，也稱常數級復雜度；數據規模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是 ，比如找n個數中的最大值；而像冒泡排序、插入排序等，數據擴大2倍，時間變慢4倍的，屬於 的復雜度。還有壹些窮舉類的算法，所需時間長度成幾何階數上漲，這就是 的指數級復雜度，甚至 的階乘級復雜度。不會存在 的復雜度，因為前面的那個“2”是系數，根本不會影響到整個程序的時間增長。同樣地， 的復雜度也就是 的復雜度。因此，我們會說，壹個 的程序的效率比 的效率低，盡管在n很小的時候，前者優於後者，但後者時間隨數據規模增長得慢，最終 的復雜度將遠遠超過 。我們也說， 的復雜度小於 的復雜度。
Ok，寫到這裏總算要引入正題了，容易看的出，前面的幾類時間復雜度可以分為兩種級別：壹種是 , , 等，我們把它叫做多項式級的復雜度，因為它的規模n出現在底數的位置；另壹種是 和 型復雜度，它是非多項式級的，其復雜度往往計算機都不能承受。
是時候引入P、NP問題的概念了： 如果壹個問題可以找到壹個能在多項式的時間復雜度裏解決它的算法，那麽這個問題就屬於P問題 。而NP問題的理解並不是NotP，NP問題不是非P類問題。 NP問題是指可以在多項式的時間裏驗證壹個解的問題，NP問題的另壹個定義是，可以在多項式的時間裏猜出壹個解的問題。 P類問題相信不用舉太多的例子來說明了，上面提到的找最大數，排序等問題都是P類問題，而要更好的理解NP問題需要另外舉壹個例子。
大整數因式分解問題-比如有人告訴妳數9938550可以分解成兩個數的乘積，妳不知道到底對不對，但是如果告訴妳這兩個數是1123和8850，那麽很容易就可以用最簡單的計算器進行驗證。
最短路徑問題-某頂點出發，沿圖的邊到達另壹頂點所經過的路徑中，各邊上權值之和最小的壹條路徑——最短路徑。
如上圖，比如告訴妳從點0到點5的最短路徑是22，要驗證的話只需要0->1,加上1->5，13+9=22，時間復雜度是常量 ，假如從上圖的六個點擴大到n個點的話，驗證過程所需要的算法時間很雜度也都是 。如果沒有告訴妳最短路徑是多要，要用算法來求解的話，我們可以這樣來“猜測”它的解：先求壹個總路程不超過 100的方案，假設我們可以依靠極好的運氣“猜出”壹個路線，使得總長度確實不超過100，那麽我們只需要每次猜壹條路壹***猜n次。接下來我們再找總長度不超過 50 的方案，找不到就將閾值提高到75…… 假設最後找到了總長度為 90 的方案，而找不到總長度小於90的方案。我們最終便在多項式時間 內“猜”到了這個旅行商問題的解是壹個長度為 90 的路線。
是否有不是NP問題的問題呢？有。就是對於那些驗證解都無法在多項式時間復雜度內完成的問題。比如問：壹個圖中是否不存在Hamilton回路？
從圖中的任意壹點出發，最終回到起點，路途中經過圖中每壹個結點當且僅當壹次，則成為哈密頓回路。
驗證Hamilton回路只需要把給定的路徑走壹次看是不是只每個結點只經過壹次，而驗證不存在Hamilton回路則需要把每條路徑都走壹遍否則不敢說不存在Hamilton回路。
之所以要特別的定義NP問題，就在於我們不會去為那些無法在多項式時間復雜度內驗證的問題去在多項式的時間復雜度內求它的解，有點拗口，但是多看幾遍應該明白，通俗的講就是對於壹個問題告訴妳答案讓妳去驗證都需要很長很長時間，可以相像要用算法去求解的話必定需要更長時間。
那麽反過來說，所有的P類問題都是NP問題。也就是說，能多項式地解決壹個問題，必然能多項式地驗證壹個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較壹下就可以了，大不了再算壹次給妳看也只需要多項式的時間復雜度。關鍵是，人們想知道，是否所有的NP問題都是P類問題，也就是說是否所有可以用多項式時間驗證的問題，也可以在多項式時間內求解。我們可以用集合的觀點來說明。如果把所有P類問題歸為壹個集合P中，把所有NP問題劃進另壹個集合NP中，那麽，顯然有P屬於NP。現在，所有對NP問題的研究都集中在壹個問題上，即究竟是否有P=NP？ 通常所謂的“NP問題”，其實就壹句話：證明或推翻P=NP。
說到這裏什麽是P類問題什麽是NP類問題就講完了。可能有壹些人還不是很清楚，再用通俗但不是很嚴謹的表述來總結壹下。
P類問題就是指那些計算機比較容易算出答案的問題。
NP類問題就是指那些已知答案以後計算機可以比較容易地驗證答案的問題。
接下來要進入的話題是為什麽P=NP難證明，覺得枯燥的看到這裏已經很好了，起碼能分清楚P和NP問題了吧，接下來的內容將比較燒腦。
我們先來看壹副集合示意圖，這副圖反映的是P=NP或P!=NP時候的兩個集合的效果，其中就出現了NP-Hard和NPC兩個新的概念。要說明為什麽目前為止P是否等於NP還沒有結論，不得不先弄清楚NPC和NP-Hard。
在引入NPC之前我們先來學習壹個概念-歸約。簡單地說，壹個問題A可以歸約為問題B的意思是說，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。舉個例子，現在有兩個問題：求解壹個壹元壹次方程和求解壹個壹元二次方程。那麽我們說，前者可以歸約為後者，因為知道怎麽樣解壹個壹元二次方程那麽壹定能解出壹元壹次方程，因為壹元壹次方程是壹個二次項系數為零的壹元二次方程。“問題A可歸約為問題B”，那麽很容易理解問題B比問題A難，要解決問題B的時間復雜度也就應該大於或等於解決問題A的時間復雜度。而且歸約有壹項重要的性質：傳遞性。如果問題A可歸約為問題B，問題B可歸約為問題C，則問題A壹定可歸約為問題C，這應該很容易理解吧。現在再來說壹下歸約的標準概念： 如果能找到這樣壹個變化法則，對任意壹個程序A的輸入，都能按這個法則變換成程序B的輸入，使兩程序的輸出相同，那麽我們說，問題A可歸約為問題B。
從歸約的定義中我們看到，壹個問題歸約為另壹個問題，時間復雜度增加了，問題的應用範圍也增大了。通過對某些問題的不斷歸約，我們能夠不斷尋找復雜度更高，但應用範圍更廣的算法來代替復雜度雖然低，但只能用於很小的壹類問題的算法。那麽如果把壹個NP問題不斷地歸約上去，那麽最後是否有可能找到壹個時間復雜度最高，並且能“通吃”所有的NP問題的這樣壹個超級NP問題？答案居然是肯定的。也就是說，存在這樣壹個NP問題，所有的NP問題都可以歸約成它，並且這種問題不只壹個，它有很多個，它是壹類問題。這壹類問題就是傳說中的NPC問題，也就是NP-完全問題。所以NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。 首先，它得是壹個NP問題；然後，所有的NP問題都可以歸約到它。
既然所有的NP問題都能歸約成NPC問題，那麽只要任意壹個NPC問題找到了壹個多項式的算法，那麽所有的NP問題都能用這個算法解決了，那麽NP也就等於P了。因此，目前NPC問題還沒有多項式的有效算法，只能用指數級甚至階乘級復雜度的算法來解決，那麽意思就是如果能夠找到壹個能用多項式時間復雜度解決的NPC問題就證明了P=NP了。
而說到NP-Hard問題。NP-Hard問題是這樣壹種問題，它滿足NPC問題定義的第二條但不壹定要滿足第壹條，就是說所有的NP問題都能歸化到它，但它本身並不壹定是個NP問題，也就是即使有壹天發現了NPC問題的多項式算法，但NP-Hard問題仍然無法用多項式算法解決，因為它不是NP問題，對於答案的驗證都很困難。
下面引用Matrix67文章裏的邏輯電路的例子來說明NPC問題。
邏輯電路問題是指的這樣壹個問題：給定壹個邏輯電路，問是否存在壹種輸入使輸出為True。
什麽叫做邏輯電路呢？壹個邏輯電路由若幹個輸入，壹個輸出，若幹“邏輯門”和密密麻麻的線組成。看下面壹例，不需要解釋妳馬上就明白了。
這是個較簡單的邏輯電路，當輸入1、輸入2、輸入3分別為True、True、False或False、True、False時，輸出為True。
有輸出無論如何都不可能為True的邏輯電路嗎？有。下面就是壹個簡單的例子。
上面這個邏輯電路中，無論輸入是什麽，輸出都是False。我們就說，這個邏輯電路不存在使輸出為True的壹組輸入。
回到上文，給定壹個邏輯電路，問是否存在壹種輸入使輸出為True，這即邏輯電路問題。
邏輯電路問題屬於NPC問題。這是有嚴格證明的。它顯然屬於NP問題，並且可以直接證明所有的NP問題都可以歸約到它。證明過程相當復雜，其大概意思是說任意壹個NP問題的輸入和輸出都可以轉換成邏輯電路的輸入和輸出（想想計算機內部也不過是壹些0和1的運算），因此對於壹個NP問題來說，問題轉化為了求出滿足結果為True的壹個輸入（即壹個可行解）。
類似這樣的NPC問題，目前還沒有找到在多項式復雜度內可以求解的算法，所以說壹旦這樣的問題都變得多項式復雜度內可解的話，很多問題都可以通過現有的計算機技術進行求解。就比如電腦下圍棋，驗證壹局棋的結果顯然是很簡單的，但要保證每局都能贏的話目前的方法需要電腦窮舉出所有的可能性，並根據每壹步棋的變化搜索出最終達到勝利的下棋路徑，目前的計算機性能顯然是達不到的。因為圍棋的狀態空間復雜度達到了10的172方，而圍棋的博弈樹復雜度達到了10的300次方，光看數字可能不直觀，壹句話就是圍棋的變化多過宇宙的原子數量！
所以對於圍棋這樣的遊戲人工智能如果要戰勝人類需要實現下面兩個條件中的任何壹個：
計算機性能無限強大，可以窮舉所有可能性；
研究出新的算法，在不窮舉的情況下也能保證贏；
目前 Google 的 AlphaGo所做的只不過是通過優化算法提高窮舉效率，同時利用現有的大數據與雲計算來提升計算性能而已 。下面壹篇文章將更詳細的介紹AI是如何下圍棋的，敬請期待。