原文地址：http://m.blog.csdn.net/csshuke/article/details/74909562

希望通過(guò)這篇文章可以不僅讓計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的人可以看懂和區(qū)分什么是P類(lèi)問(wèn)題什么是NP類(lèi)問(wèn)題暴凑，更希望達(dá)到的效果是非專(zhuān)業(yè)人士比如學(xué)文科的朋友也可以有一定程度的理解狼电。

有一則程序員界的笑話(huà)丈牢，就是有一哥們?nèi)oogle面試的時(shí)候被問(wèn)到一個(gè)問(wèn)題是：在什么情況下P=NP拓挥，然后他的回答是”當(dāng)N=1的時(shí)候”买鸽。這是我第一次聽(tīng)說(shuō)P=NP問(wèn)題央渣，大概是在臨近畢業(yè)為找工作而準(zhǔn)備的時(shí)候厌杜。
這幾天科技類(lèi)新聞的頭條都被阿爾法狗大戰(zhàn)李世石刷爆了，雖然我也不是AI專(zhuān)家畔勤，但是也想從普通人的角度來(lái)寫(xiě)點(diǎn)東西來(lái)聊聊這個(gè)有意思的事情，在搜集資料的時(shí)候又一次看到了NP問(wèn)題扒磁，于是想開(kāi)個(gè)小差庆揪，在寫(xiě)下一篇文章《AI是怎么下圍棋的?》之前，先說(shuō)說(shuō)這個(gè)NP問(wèn)題哈妨托。
最簡(jiǎn)單的定義是這樣的：
P問(wèn)題：
一個(gè)問(wèn)題可以在多項(xiàng)式（）的時(shí)間復(fù)雜度內(nèi)解決缸榛。
NP問(wèn)題：
一個(gè)問(wèn)題的解可以在多項(xiàng)式的時(shí)間內(nèi)被驗(yàn)證。
NP-hard問(wèn)題：
任意np問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)歸約為該問(wèn)題兰伤，但該問(wèn)題本身不一定是NP問(wèn)題内颗。歸約的意思是為了解決問(wèn)題A，先將問(wèn)題A歸約為另一個(gè)問(wèn)題B敦腔，解決問(wèn)題B同時(shí)也間接解決了問(wèn)題A均澳。
NPC問(wèn)題：
既是NP問(wèn)題，也是NP-hard問(wèn)題符衔。
這樣的定義雖然簡(jiǎn)單负懦，但是對(duì)于第一次接觸P、NP的人來(lái)說(shuō)柏腻，就像前一陣問(wèn)你什么是“引力波”而你回答：引力波是時(shí)空的漣漪纸厉。從答案中幾乎沒(méi)有得到任何有意義的理解。所以接來(lái)來(lái)的內(nèi)容希望不僅計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的人可以看懂五嫂，希望達(dá)到的效果是文科生們也可以有一定程度的理解颗品。
現(xiàn)階段雖然電腦已經(jīng)非常的普及肯尺，有人用它來(lái)上網(wǎng)，有用它來(lái)的游戲躯枢，有用它來(lái)看片则吟，但是很少人有還在乎電腦的本質(zhì)是計(jì)算機(jī)，它在給人們的日常生活帶來(lái)娛樂(lè)和方便的同時(shí)表現(xiàn)的其實(shí)是其龐大的計(jì)算能力锄蹂。日常生活中我們使用的各種五花八門(mén)的軟件氓仲，其實(shí)都是一組計(jì)算機(jī)程序稚伍，而程序則可以看作是一系列算法蹲缠，而我們看到的計(jì)算機(jī)的硬件的作用就是處理這些算法。這里的所說(shuō)算法不只是簡(jiǎn)單的加減乘除幔荒，而是包括下面這些要素：
算術(shù)運(yùn)算：加減乘除等運(yùn)算
邏輯運(yùn)算：或朝抖、且啥箭、非等運(yùn)算
關(guān)系運(yùn)算：大于、小于治宣、等于急侥、不等于等運(yùn)算
數(shù)據(jù)傳輸：輸入、輸出侮邀、賦值等運(yùn)算
以及通過(guò)控制結(jié)構(gòu)來(lái)控制處理這些運(yùn)算或操作的順序坏怪。說(shuō)到這里有點(diǎn)擔(dān)心有些朋友已經(jīng)不是很明白了，舉個(gè)例子吧绊茧。
我們?nèi)绾螐膎個(gè)數(shù)里面挑出最大的數(shù)陕悬。這個(gè)簡(jiǎn)單吧，就只需要一個(gè)一個(gè)數(shù)的對(duì)比過(guò)去就行了按傅。具體說(shuō)也就是先比較n和n-1捉超，記下比較大的那個(gè)數(shù)，接著我們?cè)俦容^記下的這個(gè)數(shù)和n-2唯绍，又記下比較大的數(shù)拼岳，這樣一直比到最后一個(gè)數(shù)。這整個(gè)比較的過(guò)程我們就可以把其叫作算法况芒，而這個(gè)算法就包含了上述的這些要素惜纸。給我們的n個(gè)數(shù)就是算法的輸入數(shù)據(jù)，我們要挑選出最大的那個(gè)數(shù)就是算法的輸出數(shù)據(jù)绝骚，當(dāng)中我們判斷大小的時(shí)候必然采用了一些基礎(chǔ)的算術(shù)運(yùn)算或關(guān)系運(yùn)算耐版。
希望說(shuō)到這里大家能夠基本理解什么是算法，因?yàn)榻酉聛?lái)我要花一點(diǎn)時(shí)間說(shuō)說(shuō)什么是算法的時(shí)間復(fù)雜度压汪。要計(jì)算或解決一個(gè)問(wèn)題粪牲，該問(wèn)題通常有一個(gè)大小規(guī)模，用n表示止剖。我們還是引用上面的例子腺阳，從n個(gè)數(shù)里面找出最大的那個(gè)數(shù)落君，這個(gè)n就是該問(wèn)題的規(guī)模大小。怎么找呢亭引？我們要通過(guò)比較n-1次才能得到結(jié)果绎速，這個(gè)n-1次就可以理解為所花的時(shí)間，也就是時(shí)間復(fù)雜度焙蚓。再比如纹冤，將這n個(gè)數(shù)按從大至小排序，n是其規(guī)模大小，若是我們按照這樣的方法：第一次從n個(gè)數(shù)里找最大，第二次從n-1個(gè)數(shù)里找最大，以此類(lèi)推，需要的比較次數(shù)就是n(n-1)/2。我們所用的方法稱(chēng)之庫(kù)為算法薛躬，那么n(n-1)/2就是該算法的時(shí)間復(fù)雜度。對(duì)于時(shí)間復(fù)雜度坑夯，當(dāng)n足夠大時(shí)慎璧，我們只注重最高次方的那一項(xiàng)厌处，其他各項(xiàng)可以忽略捷绒，另外，其常數(shù)系數(shù)也不重要，所以些举，n(n-1)/2我們只重視n的平方這一項(xiàng)了挪挤，記為幢码，這就是該算法對(duì)該問(wèn)題的時(shí)間復(fù)雜度的專(zhuān)業(yè)表示。
時(shí)間復(fù)雜度其實(shí)并不是表示一個(gè)程序解決問(wèn)題具體需要花多少時(shí)間，而是當(dāng)問(wèn)題規(guī)模擴(kuò)大后辕坝，程序需要的時(shí)間長(zhǎng)度增長(zhǎng)得有多快。也就是說(shuō)，對(duì)于高速處理數(shù)據(jù)的計(jì)算機(jī)來(lái)說(shuō)樊诺，處理某一個(gè)特定數(shù)據(jù)的效率不能衡量一個(gè)程序的好壞秃嗜，而應(yīng)該看當(dāng)這個(gè)數(shù)據(jù)的規(guī)模變大到數(shù)百倍后虽惭，程序運(yùn)行時(shí)間是否還是一樣，或者也跟著慢了數(shù)百倍炮捧，或者變慢了數(shù)萬(wàn)倍。不管數(shù)據(jù)有多大惦银，程序處理花的時(shí)間始終是那么多的咆课，我們就說(shuō)這個(gè)程序很好，具有的時(shí)間復(fù)雜度扯俱，也稱(chēng)常數(shù)級(jí)復(fù)雜度书蚪；數(shù)據(jù)規(guī)模變得有多大，花的時(shí)間也跟著變得有多長(zhǎng)迅栅，這個(gè)程序的時(shí)間復(fù)雜度就是殊校，比如找n個(gè)數(shù)中的最大值；而像冒泡排序读存、插入排序等为流，數(shù)據(jù)擴(kuò)大2倍呕屎，時(shí)間變慢4倍的，屬于的復(fù)雜度敬察。還有一些窮舉類(lèi)的算法秀睛，所需時(shí)間長(zhǎng)度成幾何階數(shù)上漲，這就是的指數(shù)級(jí)復(fù)雜度静汤，甚至的階乘級(jí)復(fù)雜度琅催。不會(huì)存在的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)虫给，根本不會(huì)影響到整個(gè)程序的時(shí)間增長(zhǎng)藤抡。同樣地，的復(fù)雜度也就是的復(fù)雜度抹估。因此缠黍，我們會(huì)說(shuō)，一個(gè)的程序的效率比的效率低药蜻，盡管在n很小的時(shí)候瓷式，前者優(yōu)于后者，但后者時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)得慢语泽，最終的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過(guò)贸典。我們也說(shuō)，的復(fù)雜度小于的復(fù)雜度踱卵。
Ok廊驼，寫(xiě)到這里總算要引入正題了，容易看的出惋砂，前面的幾類(lèi)時(shí)間復(fù)雜度可以分為兩種級(jí)別：一種是,,等妒挎，我們把它叫做多項(xiàng)式級(jí)的復(fù)雜度，因?yàn)樗囊?guī)模n出現(xiàn)在底數(shù)的位置西饵；另一種是和型復(fù)雜度酝掩，它是非多項(xiàng)式級(jí)的，其復(fù)雜度往往計(jì)算機(jī)都不能承受眷柔。
是時(shí)候引入P期虾、NP問(wèn)題的概念了：如果一個(gè)問(wèn)題可以找到一個(gè)能在多項(xiàng)式的時(shí)間復(fù)雜度里解決它的算法，那么這個(gè)問(wèn)題就屬于P問(wèn)題驯嘱。而NP問(wèn)題的理解并不是NotP镶苞，NP問(wèn)題不是非P類(lèi)問(wèn)題。NP問(wèn)題是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問(wèn)題宙拉，NP問(wèn)題的另一個(gè)定義是宾尚，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的問(wèn)題。P類(lèi)問(wèn)題相信不用舉太多的例子來(lái)說(shuō)明了，上面提到的找最大數(shù)煌贴，排序等問(wèn)題都是P類(lèi)問(wèn)題御板，而要更好的理解NP問(wèn)題需要另外舉一個(gè)例子。
大整數(shù)因式分解問(wèn)題-比如有人告訴你數(shù)9938550可以分解成兩個(gè)數(shù)的乘積牛郑，你不知道到底對(duì)不對(duì)怠肋，但是如果告訴你這兩個(gè)數(shù)是1123和8850，那么很容易就可以用最簡(jiǎn)單的計(jì)算器進(jìn)行驗(yàn)證淹朋。
最短路徑問(wèn)題-某頂點(diǎn)出發(fā)笙各，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑础芍。

如上圖杈抢，比如告訴你從點(diǎn)0到點(diǎn)5的最短路徑是22，要驗(yàn)證的話(huà)只需要0->1,加上1->5仑性，13+9=22惶楼，時(shí)間復(fù)雜度是常量，假如從上圖的六個(gè)點(diǎn)擴(kuò)大到n個(gè)點(diǎn)的話(huà)诊杆，驗(yàn)證過(guò)程所需要的算法時(shí)間很雜度也都是歼捐。如果沒(méi)有告訴你最短路徑是多要，要用算法來(lái)求解的話(huà)晨汹，我們可以這樣來(lái)“猜測(cè)”它的解：先求一個(gè)總路程不超過(guò) 100的方案豹储，假設(shè)我們可以依靠極好的運(yùn)氣“猜出”一個(gè)路線，使得總長(zhǎng)度確實(shí)不超過(guò)100淘这，那么我們只需要每次猜一條路一共猜n次剥扣。接下來(lái)我們?cè)僬铱傞L(zhǎng)度不超過(guò) 50 的方案，找不到就將閾值提高到75…… 假設(shè)最后找到了總長(zhǎng)度為 90 的方案慨灭，而找不到總長(zhǎng)度小于90的方案朦乏。我們最終便在多項(xiàng)式時(shí)間內(nèi)“猜”到了這個(gè)旅行商問(wèn)題的解是一個(gè)長(zhǎng)度為 90 的路線球及。
是否有不是NP問(wèn)題的問(wèn)題呢氧骤？有。就是對(duì)于那些驗(yàn)證解都無(wú)法在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)完成的問(wèn)題吃引。比如問(wèn)：一個(gè)圖中是否不存在Hamilton回路筹陵？
從圖中的任意一點(diǎn)出發(fā)，最終回到起點(diǎn)镊尺，路途中經(jīng)過(guò)圖中每一個(gè)結(jié)點(diǎn)當(dāng)且僅當(dāng)一次朦佩，則成為哈密頓回路。
驗(yàn)證Hamilton回路只需要把給定的路徑走一次看是不是只每個(gè)結(jié)點(diǎn)只經(jīng)過(guò)一次庐氮，而驗(yàn)證不存在Hamilton回路則需要把每條路徑都走一遍否則不敢說(shuō)不存在Hamilton回路语稠。
之所以要特別的定義NP問(wèn)題，就在于我們不會(huì)去為那些無(wú)法在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)驗(yàn)證的問(wèn)題去在多項(xiàng)式的時(shí)間復(fù)雜度內(nèi)求它的解，有點(diǎn)拗口仙畦，但是多看幾遍應(yīng)該明白输涕，通俗的講就是對(duì)于一個(gè)問(wèn)題告訴你答案讓你去驗(yàn)證都需要很長(zhǎng)很長(zhǎng)時(shí)間，可以相像要用算法去求解的話(huà)必定需要更長(zhǎng)時(shí)間慨畸。
那么反過(guò)來(lái)說(shuō)莱坎，所有的P類(lèi)問(wèn)題都是NP問(wèn)題。也就是說(shuō)寸士，能多項(xiàng)式地解決一個(gè)問(wèn)題檐什，必然能多項(xiàng)式地驗(yàn)證一個(gè)問(wèn)題的解——既然正解都出來(lái)了，驗(yàn)證任意給定的解也只需要比較一下就可以了弱卡，大不了再算一次給你看也只需要多項(xiàng)式的時(shí)間復(fù)雜度乃正。關(guān)鍵是，人們想知道婶博，是否所有的NP問(wèn)題都是P類(lèi)問(wèn)題烫葬，也就是說(shuō)是否所有可以用多項(xiàng)式時(shí)間驗(yàn)證的問(wèn)題，也可以在多項(xiàng)式時(shí)間內(nèi)求解凡蜻。我們可以用集合的觀點(diǎn)來(lái)說(shuō)明搭综。如果把所有P類(lèi)問(wèn)題歸為一個(gè)集合P中，把所有NP問(wèn)題劃進(jìn)另一個(gè)集合NP中划栓，那么兑巾，顯然有P屬于NP。現(xiàn)在忠荞，所有對(duì)NP問(wèn)題的研究都集中在一個(gè)問(wèn)題上蒋歌，即究竟是否有P=NP？通常所謂的“NP問(wèn)題”委煤，其實(shí)就一句話(huà)：證明或推翻P=NP堂油。
說(shuō)到這里什么是P類(lèi)問(wèn)題什么是NP類(lèi)問(wèn)題就講完了”探剩可能有一些人還不是很清楚府框，再用通俗但不是很?chē)?yán)謹(jǐn)?shù)谋硎鰜?lái)總結(jié)一下。
P類(lèi)問(wèn)題就是指那些計(jì)算機(jī)比較容易算出答案的問(wèn)題讥邻。
NP類(lèi)問(wèn)題就是指那些已知答案以后計(jì)算機(jī)可以比較容易地驗(yàn)證答案的問(wèn)題迫靖。
接下來(lái)要進(jìn)入的話(huà)題是為什么P=NP難證明，覺(jué)得枯燥的看到這里已經(jīng)很好了兴使，起碼能分清楚P和NP問(wèn)題了吧系宜，接下來(lái)的內(nèi)容將比較燒腦。

我們先來(lái)看一副集合示意圖发魄，這副圖反映的是P=NP或P!=NP時(shí)候的兩個(gè)集合的效果盹牧，其中就出現(xiàn)了NP-Hard和NPC兩個(gè)新的概念。要說(shuō)明為什么目前為止P是否等于NP還沒(méi)有結(jié)論，不得不先弄清楚NPC和NP-Hard汰寓。
在引入NPC之前我們先來(lái)學(xué)習(xí)一個(gè)概念-歸約吆寨。簡(jiǎn)單地說(shuō)，一個(gè)問(wèn)題A可以歸約為問(wèn)題B的意思是說(shuō)踩寇，可以用問(wèn)題B的解法解決問(wèn)題A啄清，或者說(shuō)，問(wèn)題A可以“變成”問(wèn)題B俺孙。舉個(gè)例子辣卒，現(xiàn)在有兩個(gè)問(wèn)題：求解一個(gè)一元一次方程和求解一個(gè)一元二次方程。那么我們說(shuō)睛榄，前者可以歸約為后者荣茫，因?yàn)橹涝趺礃咏庖粋€(gè)一元二次方程那么一定能解出一元一次方程，因?yàn)橐辉淮畏匠淌且粋€(gè)二次項(xiàng)系數(shù)為零的一元二次方程场靴》壤颍“問(wèn)題A可歸約為問(wèn)題B”，那么很容易理解問(wèn)題B比問(wèn)題A難旨剥，要解決問(wèn)題B的時(shí)間復(fù)雜度也就應(yīng)該大于或等于解決問(wèn)題A的時(shí)間復(fù)雜度咧欣。而且歸約有一項(xiàng)重要的性質(zhì)：傳遞性。如果問(wèn)題A可歸約為問(wèn)題B轨帜，問(wèn)題B可歸約為問(wèn)題C魄咕，則問(wèn)題A一定可歸約為問(wèn)題C，這應(yīng)該很容易理解吧“龈福現(xiàn)在再來(lái)說(shuō)一下歸約的標(biāo)準(zhǔn)概念：如果能找到這樣一個(gè)變化法則哮兰，對(duì)任意一個(gè)程序A的輸入，都能按這個(gè)法則變換成程序B的輸入苟弛，使兩程序的輸出相同喝滞，那么我們說(shuō)，問(wèn)題A可歸約為問(wèn)題B膏秫。
從歸約的定義中我們看到右遭，一個(gè)問(wèn)題歸約為另一個(gè)問(wèn)題，時(shí)間復(fù)雜度增加了荔睹，問(wèn)題的應(yīng)用范圍也增大了狸演。通過(guò)對(duì)某些問(wèn)題的不斷歸約言蛇，我們能夠不斷尋找復(fù)雜度更高僻他，但應(yīng)用范圍更廣的算法來(lái)代替復(fù)雜度雖然低，但只能用于很小的一類(lèi)問(wèn)題的算法腊尚。那么如果把一個(gè)NP問(wèn)題不斷地歸約上去吨拗，那么最后是否有可能找到一個(gè)時(shí)間復(fù)雜度最高，并且能“通吃”所有的NP問(wèn)題的這樣一個(gè)超級(jí)NP問(wèn)題？答案居然是肯定的劝篷。也就是說(shuō)哨鸭，存在這樣一個(gè)NP問(wèn)題，所有的NP問(wèn)題都可以歸約成它娇妓，并且這種問(wèn)題不只一個(gè)像鸡，它有很多個(gè)，它是一類(lèi)問(wèn)題哈恰。這一類(lèi)問(wèn)題就是傳說(shuō)中的NPC問(wèn)題只估，也就是NP-完全問(wèn)題。所以NPC問(wèn)題的定義非常簡(jiǎn)單着绷。同時(shí)滿(mǎn)足下面兩個(gè)條件的問(wèn)題就是NPC問(wèn)題蛔钙。首先，它得是一個(gè)NP問(wèn)題荠医；然后吁脱，所有的NP問(wèn)題都可以歸約到它。
既然所有的NP問(wèn)題都能歸約成NPC問(wèn)題彬向，那么只要任意一個(gè)NPC問(wèn)題找到了一個(gè)多項(xiàng)式的算法兼贡，那么所有的NP問(wèn)題都能用這個(gè)算法解決了，那么NP也就等于P了娃胆。因此紧显，目前NPC問(wèn)題還沒(méi)有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的算法來(lái)解決缕棵，那么意思就是如果能夠找到一個(gè)能用多項(xiàng)式時(shí)間復(fù)雜度解決的NPC問(wèn)題就證明了P=NP了孵班。
而說(shuō)到NP-Hard問(wèn)題。NP-Hard問(wèn)題是這樣一種問(wèn)題招驴，它滿(mǎn)足NPC問(wèn)題定義的第二條但不一定要滿(mǎn)足第一條篙程，就是說(shuō)所有的NP問(wèn)題都能歸化到它，但它本身并不一定是個(gè)NP問(wèn)題别厘，也就是即使有一天發(fā)現(xiàn)了NPC問(wèn)題的多項(xiàng)式算法虱饿，但NP-Hard問(wèn)題仍然無(wú)法用多項(xiàng)式算法解決，因?yàn)樗皇荖P問(wèn)題触趴，對(duì)于答案的驗(yàn)證都很困難氮发。
下面引用Matrix67文章里的邏輯電路的例子來(lái)說(shuō)明NPC問(wèn)題。
邏輯電路問(wèn)題是指的這樣一個(gè)問(wèn)題：給定一個(gè)邏輯電路冗懦，問(wèn)是否存在一種輸入使輸出為T(mén)rue爽冕。
什么叫做邏輯電路呢？一個(gè)邏輯電路由若干個(gè)輸入披蕉，一個(gè)輸出颈畸，若干“邏輯門(mén)”和密密麻麻的線組成乌奇。看下面一例眯娱，不需要解釋你馬上就明白了礁苗。

這是個(gè)較簡(jiǎn)單的邏輯電路，當(dāng)輸入1徙缴、輸入2试伙、輸入3分別為T(mén)rue、True于样、False或False迁霎、True、False時(shí)百宇，輸出為T(mén)rue考廉。
有輸出無(wú)論如何都不可能為T(mén)rue的邏輯電路嗎？有携御。下面就是一個(gè)簡(jiǎn)單的例子昌粤。

上面這個(gè)邏輯電路中，無(wú)論輸入是什么啄刹，輸出都是False涮坐。我們就說(shuō)，這個(gè)邏輯電路不存在使輸出為T(mén)rue的一組輸入誓军。
回到上文袱讹，給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為T(mén)rue昵时，這即邏輯電路問(wèn)題捷雕。
邏輯電路問(wèn)題屬于NPC問(wèn)題。這是有嚴(yán)格證明的壹甥。它顯然屬于NP問(wèn)題救巷，并且可以直接證明所有的NP問(wèn)題都可以歸約到它。證明過(guò)程相當(dāng)復(fù)雜句柠，其大概意思是說(shuō)任意一個(gè)NP問(wèn)題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計(jì)算機(jī)內(nèi)部也不過(guò)是一些0和1的運(yùn)算）浦译，因此對(duì)于一個(gè)NP問(wèn)題來(lái)說(shuō)，問(wèn)題轉(zhuǎn)化為了求出滿(mǎn)足結(jié)果為T(mén)rue的一個(gè)輸入（即一個(gè)可行解）溯职。
類(lèi)似這樣的NPC問(wèn)題精盅，目前還沒(méi)有找到在多項(xiàng)式復(fù)雜度內(nèi)可以求解的算法，所以說(shuō)一旦這樣的問(wèn)題都變得多項(xiàng)式復(fù)雜度內(nèi)可解的話(huà)谜酒，很多問(wèn)題都可以通過(guò)現(xiàn)有的計(jì)算機(jī)技術(shù)進(jìn)行求解叹俏。就比如電腦下圍棋，驗(yàn)證一局棋的結(jié)果顯然是很簡(jiǎn)單的甚带，但要保證每局都能贏的話(huà)目前的方法需要電腦窮舉出所有的可能性她肯，并根據(jù)每一步棋的變化搜索出最終達(dá)到勝利的下棋路徑佳头，目前的計(jì)算機(jī)性能顯然是達(dá)不到的鹰贵。因?yàn)閲宓臓顟B(tài)空間復(fù)雜度達(dá)到了10的172方晴氨，而圍棋的博弈樹(shù)復(fù)雜度達(dá)到了10的300次方，光看數(shù)字可能不直觀碉输，一句話(huà)就是圍棋的變化多過(guò)宇宙的原子數(shù)量籽前！
所以對(duì)于圍棋這樣的游戲人工智能如果要戰(zhàn)勝人類(lèi)需要實(shí)現(xiàn)下面兩個(gè)條件中的任何一個(gè)：
計(jì)算機(jī)性能無(wú)限強(qiáng)大，可以窮舉所有可能性敷钾；
研究出新的算法枝哄，在不窮舉的情況下也能保證贏；
目前 Google 的 AlphaGo所做的只不過(guò)是通過(guò)優(yōu)化算法提高窮舉效率阻荒，同時(shí)利用現(xiàn)有的大數(shù)據(jù)與云計(jì)算來(lái)提升計(jì)算性能而已 挠锥。下面一篇文章將更詳細(xì)的介紹AI是如何下圍棋的，敬請(qǐng)期待侨赡。