家都知道NP-10是一種非常普及的洗滌原料，乳化，滲透效果很好，成本平民化，曾經(jīng)風(fēng)靡一時(shí)，但是她曾經(jīng)的優(yōu)點(diǎn)卻變成了今日的缺點(diǎn)。NP-10的主要成分是由壬基酚團(tuán)構(gòu)成，COD也偏高，與保護(hù)環(huán)境沖突嚴(yán)重。現(xiàn)在許多國(guó)家禁止使用含有壬基酚團(tuán)的產(chǎn)品。但生活還是要繼續(xù)，這導(dǎo)致了下游公司不得不研發(fā)新產(chǎn)品去取代NP-10。經(jīng)過(guò)一段時(shí)間的研發(fā)，現(xiàn)在市場(chǎng)上研發(fā)出了一些代替品如：阿克蘇Berol185，阿克蘇Ethylan 1005, 潔氏C13異丙醇酰胺，月桂醇磷酸酯MAE等等。這些代替品在環(huán)保方面可以取代NP-10,但也不是能完全取代，且價(jià)格是NP-10的兩倍以上。近期找到了一種不含壬基酚團(tuán)，不含磷，氮的材料NPO-10乳化劑在功能上可以代替NP-10。價(jià)格也很接近。可以放心使用。
NPO-10是無(wú)色透明液體，屬非離子表面活性劑，親水性優(yōu)良，由于主要成分是脂肪醇，濁點(diǎn)75-95°C凍點(diǎn)≤5°C 使用溫度（5°-95°）！由于HLB值13.8-14.5，其乳化/滲透/分散/抗硬水等性能明顯優(yōu)于純?nèi)苫泳垩跻蚁┟讶榛瘎PO-10與烷基胺酯OTE,665T表面活性劑復(fù)配可得一款制作簡(jiǎn)單，超級(jí)環(huán)保的洗潔精。
產(chǎn)品用途：廣泛用于金屬表面處理劑、工業(yè)及日化洗滌、脫漆劑、潤(rùn)濕劑、紡織加工、印染、石化冶煉、農(nóng)藥乳化、采礦浮選、涂料、造紙、皮革等工業(yè)。
大家好，我是貓哥。我最近在追一部熱播的電視劇《天才基本法》，它反復(fù)提到了“P=NP”問(wèn)題。這可是一個(gè)天大的難題，在 2000 年克雷數(shù)學(xué)研究所公布的千禧年七大數(shù)學(xué)難題中，P 和 NP 問(wèn)題排在了第一位！網(wǎng)上有比較多的科普文章，但較多為泛泛而談。經(jīng)過(guò)仔細(xì)篩選，我今天給大家分享一篇長(zhǎng)文，大家可以收藏慢慢閱讀。（PS：以下內(nèi)容為作者 2006 年及 2022 年兩篇文章合并而成，為便于閱讀，內(nèi)容略有改動(dòng)。）
作者：Matrix67
來(lái)源：http://www.matrix67.com/blog/archives/105
你會(huì)經(jīng)常看到網(wǎng)上出現(xiàn)“這怎么做，這不是NP問(wèn)題嗎”、“這個(gè)只有搜了，這已經(jīng)被證明是NP問(wèn)題了”之類的話。這或許是眾多OIer最大的誤區(qū)之一。你要知道，大多數(shù)人此時(shí)所說(shuō)的NP問(wèn)題其實(shí)都是指的NPC問(wèn)題。他們沒(méi)有搞清楚NP問(wèn)題和NPC問(wèn)題的概念。NP問(wèn)題并不是那種“只有搜才行”的問(wèn)題，NPC問(wèn)題才是。
好，行了，基本上這個(gè)誤解已經(jīng)被澄清了。下面的內(nèi)容都是在講什么是P問(wèn)題，什么是NP問(wèn)題，什么是NPC問(wèn)題，你如果不是很感興趣就可以不看了。接下來(lái)你可以看到，把NP問(wèn)題當(dāng)成是 NPC問(wèn)題是一個(gè)多大的錯(cuò)誤。
還是先用幾句話簡(jiǎn)單說(shuō)明一下時(shí)間復(fù)雜度。時(shí)間復(fù)雜度并不是表示一個(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è)程序很好，具有O(1)的時(shí)間復(fù)雜度，也稱常數(shù)級(jí)復(fù)雜度；數(shù)據(jù)規(guī)模變得有多大，花的時(shí)間也跟著變得有多長(zhǎng)，這個(gè)程序的時(shí)間復(fù)雜度就是O(n)，比如找n個(gè)數(shù)中的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴(kuò)大2倍，時(shí)間變慢4倍的，屬于O(n^2)的復(fù)雜度。
還有一些窮舉類的算法，所需時(shí)間長(zhǎng)度成幾何階數(shù)上漲，這就是O(a^n)的指數(shù)級(jí)復(fù)雜度，甚至O(n!)的階乘級(jí)復(fù)雜度。不會(huì)存在O(2*n^2)的復(fù)雜度，因?yàn)榍懊娴哪莻€(gè)“2”是系數(shù)，根本不會(huì)影響到整個(gè)程序的時(shí)間增長(zhǎng)。同樣地，O (n^3+n^2)的復(fù)雜度也就是O(n^3)的復(fù)雜度。
因此，我們會(huì)說(shuō)，一個(gè)O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，盡管在n很小的時(shí)候，前者優(yōu)于后者，但后者時(shí)間隨數(shù)據(jù)規(guī)模增長(zhǎng)得慢，最終O(n^3)的復(fù)雜度將遠(yuǎn)遠(yuǎn)超過(guò)O(n^2)。我們也說(shuō)，O(n^100)的復(fù)雜度小于O(1.01^n)的復(fù)雜度。
容易看出，前面的幾類復(fù)雜度被分為兩種級(jí)別，其中后者的復(fù)雜度無(wú)論如何都遠(yuǎn)遠(yuǎn)大于前者：一種是O(1)，O(log(n))，O(n^a)等，我們把它叫做多項(xiàng)式級(jí)的復(fù)雜度，因?yàn)樗囊?guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復(fù)雜度，它是非多項(xiàng)式級(jí)的，其復(fù)雜度計(jì)算機(jī)往往不能承受。
當(dāng)我們?cè)诮鉀Q一個(gè)問(wèn)題時(shí)，我們選擇的算法通常都需要是多項(xiàng)式級(jí)的復(fù)雜度，非多項(xiàng)式級(jí)的復(fù)雜度需要的時(shí)間太多，往往會(huì)超時(shí)，除非是數(shù)據(jù)規(guī)模非常小。
自然地，人們會(huì)想到一個(gè)問(wèn)題：會(huì)不會(huì)所有的問(wèn)題都可以找到復(fù)雜度為多項(xiàng)式級(jí)的算法呢？很遺憾，答案是否定的。有些問(wèn)題甚至根本不可能找到一個(gè)正確的算法來(lái)，這稱之為“不可解問(wèn)題”(Undecidable Decision Problem)。The Halting Problem就是一個(gè)著名的不可解問(wèn)題，在我的Blog上有過(guò)專門的介紹和證明。再比如，輸出從1到n這n個(gè)數(shù)的全排列。不管你用什么方法，你的復(fù)雜度都是階乘級(jí)，因?yàn)槟憧偟糜秒A乘級(jí)的時(shí)間打印出結(jié)果來(lái)。
有人說(shuō)，這樣的“問(wèn)題”不是一個(gè)“正規(guī)”的問(wèn)題，正規(guī)的問(wèn)題是讓程序解決一個(gè)問(wèn)題，輸出一個(gè)“YES”或“NO”（這被稱為判定性問(wèn)題），或者一個(gè)什么什么的最優(yōu)值（這被稱為最優(yōu)化問(wèn)題）。那么，根據(jù)這個(gè)定義，我也能舉出一個(gè)不大可能會(huì)有多項(xiàng)式級(jí)算法的問(wèn)題來(lái)：Hamilton回路。
問(wèn)題是這樣的：給你一個(gè)圖，問(wèn)你能否找到一條經(jīng)過(guò)每個(gè)頂點(diǎn)一次且恰好一次（不遺漏也不重復(fù)）最后又走回來(lái)的路（滿足這個(gè)條件的路徑叫做Hamilton回路）。這個(gè)問(wèn)題現(xiàn)在還沒(méi)有找到多項(xiàng)式級(jí)的算法。事實(shí)上，這個(gè)問(wèn)題就是我們后面要說(shuō)的NPC問(wèn)題。
下面引入P類問(wèn)題的概念：如果一個(gè)問(wèn)題可以找到一個(gè)能在多項(xiàng)式的時(shí)間里解決它的算法，那么這個(gè)問(wèn)題就屬于P問(wèn)題。P是英文單詞多項(xiàng)式的第一個(gè)字母。哪些問(wèn)題是P類問(wèn)題呢？通常NOI和NOIP不會(huì)出不屬于P類問(wèn)題的題目。我們常見(jiàn)到的一些信息奧賽的題目都是P問(wèn)題。道理很簡(jiǎn)單，一個(gè)用窮舉換來(lái)的非多項(xiàng)式級(jí)時(shí)間的超時(shí)程序不會(huì)涵蓋任何有價(jià)值的算法。
接下來(lái)引入NP問(wèn)題的概念。這個(gè)就有點(diǎn)難理解了，或者說(shuō)容易理解錯(cuò)誤。在這里強(qiáng)調(diào)（回到我竭力想澄清的誤區(qū)上），NP問(wèn)題不是非P類問(wèn)題。NP問(wèn)題是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問(wèn)題。NP問(wèn)題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的問(wèn)題。
比方說(shuō)，我RP很好，在程序中需要枚舉時(shí)，我可以一猜一個(gè)準(zhǔn)。現(xiàn)在某人拿到了一個(gè)求最短路徑的問(wèn)題，問(wèn)從起點(diǎn)到終點(diǎn)是否有一條小于100個(gè)單位長(zhǎng)度的路線。它根據(jù)數(shù)據(jù)畫(huà)好了圖，但怎么也算不出來(lái)，于是來(lái)問(wèn)我：你看怎么選條路走得最少？我說(shuō)，我RP很好，肯定能隨便給你指條很短的路出來(lái)。然后我就胡亂畫(huà)了幾條線，說(shuō)就這條吧。那人按我指的這條把權(quán)值加起來(lái)一看，嘿，神了，路徑長(zhǎng)度98，比100小。于是答案出來(lái)了，存在比100小的路徑。別人會(huì)問(wèn)他這題怎么做出來(lái)的，他就可以說(shuō)，因?yàn)槲艺业搅艘粋€(gè)比100 小的解。
在這個(gè)題中，找一個(gè)解很困難，但驗(yàn)證一個(gè)解很容易。驗(yàn)證一個(gè)解只需要O(n)的時(shí)間復(fù)雜度，也就是說(shuō)我可以花O(n)的時(shí)間把我猜的路徑的長(zhǎng)度加出來(lái)。那么，只要我RP好，猜得準(zhǔn)，我一定能在多項(xiàng)式的時(shí)間里解決這個(gè)問(wèn)題。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會(huì)來(lái)騙我去選它。這就是NP問(wèn)題。
當(dāng)然有不是NP問(wèn)題的問(wèn)題，即你猜到了解但是沒(méi)用，因?yàn)槟悴荒茉诙囗?xiàng)式的時(shí)間里去驗(yàn)證它。下面我要舉的例子是一個(gè)經(jīng)典的例子，它指出了一個(gè)目前還沒(méi)有辦法在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問(wèn)題。很顯然，前面所說(shuō)的Hamilton回路是NP問(wèn)題，因?yàn)轵?yàn)證一條路是否恰好經(jīng)過(guò)了每一個(gè)頂點(diǎn)非常容易。但我要把問(wèn)題換成這樣：試問(wèn)一個(gè)圖中是否不存在Hamilton回路。這樣問(wèn)題就沒(méi)法在多項(xiàng)式的時(shí)間里進(jìn)行驗(yàn)證了，因?yàn)槌悄阍囘^(guò)所有的路，否則你不敢斷定它“沒(méi)有Hamilton回路”。
之所以要定義NP問(wèn)題，是因?yàn)橥ǔＶ挥蠳P問(wèn)題才可能找到多項(xiàng)式的算法。我們不會(huì)指望一個(gè)連多項(xiàng)式地驗(yàn)證一個(gè)解都不行的問(wèn)題存在一個(gè)解決它的多項(xiàng)式級(jí)的算法。相信讀者很快明白，信息學(xué)中的號(hào)稱最困難的問(wèn)題——“NP問(wèn)題”，實(shí)際上是在探討NP問(wèn)題與P類問(wèn)題的關(guān)系。
很顯然，所有的P類問(wèn)題都是NP問(wèn)題。也就是說(shuō)，能多項(xiàng)式地解決一個(gè)問(wèn)題，必然能多項(xiàng)式地驗(yàn)證一個(gè)問(wèn)題的解——既然正解都出來(lái)了，驗(yàn)證任意給定的解也只需要比較一下就可以了。關(guān)鍵是，人們想知道，是否所有的NP問(wèn)題都是P類問(wèn)題。
我們可以再用集合的觀點(diǎn)來(lái)說(shuō)明。如果把所有P類問(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í)就一句話：證明或推翻P=NP。
NP問(wèn)題一直都是信息學(xué)的巔峰。巔峰，意即很引人注目但難以解決。在信息學(xué)研究中，這是一個(gè)耗費(fèi)了很多時(shí)間和精力也沒(méi)有解決的終極問(wèn)題，好比物理學(xué)中的大統(tǒng)一和數(shù)學(xué)中的歌德巴赫猜想等。
目前為止這個(gè)問(wèn)題還“啃不動(dòng)”。但是，一個(gè)總的趨勢(shì)、一個(gè)大方向是有的。人們普遍認(rèn)為，P=NP不成立，也就是說(shuō)，多數(shù)人相信，存在至少一個(gè)不可能有多項(xiàng)式級(jí)復(fù)雜度的算法的NP問(wèn)題。
人們?nèi)绱藞?jiān)信P≠NP是有原因的，就是在研究NP問(wèn)題的過(guò)程中找出了一類非常特殊的NP問(wèn)題叫做NP-完全問(wèn)題，也即所謂的 NPC問(wèn)題。C是英文單詞“完全”的第一個(gè)字母。正是NPC問(wèn)題的存在，使人們相信P≠NP。下文將花大量篇幅介紹NPC問(wèn)題，你從中可以體會(huì)到NPC問(wèn)題使P=NP變得多么不可思議。
為了說(shuō)明NPC問(wèn)題，我們先引入一個(gè)概念——約化(Reducibility，有的資料上叫“歸約”)。
簡(jiǎn)單地說(shuō)，一個(gè)問(wèn)題A可以約化為問(wèn)題B的含義即是，可以用問(wèn)題B的解法解決問(wèn)題A，或者說(shuō)，問(wèn)題A可以“變成”問(wèn)題B。
《算法導(dǎo)論》上舉了這么一個(gè)例子。比如說(shuō)，現(xiàn)在有兩個(gè)問(wèn)題：求解一個(gè)一元一次方程和求解一個(gè)一元二次方程。那么我們說(shuō)，前者可以約化為后者，意即知道如何解一個(gè)一元二次方程那么一定能解出一元一次方程。我們可以寫(xiě)出兩個(gè)程序分別對(duì)應(yīng)兩個(gè)問(wèn)題，那么我們能找到一個(gè)“規(guī)則”，按照這個(gè)規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方程的程序上，兩個(gè)程序總能得到一樣的結(jié)果。這個(gè)規(guī)則即是：兩個(gè)方程的對(duì)應(yīng)項(xiàng)系數(shù)不變，一元二次方程的二次項(xiàng)系數(shù)為0。按照這個(gè)規(guī)則把前一個(gè)問(wèn)題轉(zhuǎn)換成后一個(gè)問(wèn)題，兩個(gè)問(wèn)題就等價(jià)了。
同樣地，我們可以說(shuō)，Hamilton回路可以約化為TSP問(wèn)題(Travelling Salesman Problem，旅行商問(wèn)題)：在Hamilton回路問(wèn)題中，兩點(diǎn)相連即這兩點(diǎn)距離為0，兩點(diǎn)不直接相連則令其距離為1，于是問(wèn)題轉(zhuǎn)化為在TSP問(wèn)題中，是否存在一條長(zhǎng)為0的路徑。Hamilton回路存在當(dāng)且僅當(dāng)TSP問(wèn)題中存在長(zhǎng)為0的回路。
“問(wèn)題A可約化為問(wèn)題B”有一個(gè)重要的直觀意義：B的時(shí)間復(fù)雜度高于或者等于A的時(shí)間復(fù)雜度。也就是說(shuō)，問(wèn)題A不比問(wèn)題B難。這很容易理解。既然問(wèn)題A能用問(wèn)題B來(lái)解決，倘若B的時(shí)間復(fù)雜度比A的時(shí)間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時(shí)間復(fù)雜度還是相同。正如解一元二次方程比解一元一次方程難，因?yàn)榻鉀Q前者的方法可以用來(lái)解決后者。
很顯然，約化具有一項(xiàng)重要的性質(zhì)：約化具有傳遞性。如果問(wèn)題A可約化為問(wèn)題B，問(wèn)題B可約化為問(wèn)題C，則問(wèn)題A一定可約化為問(wèn)題C。這個(gè)道理非常簡(jiǎn)單，就不必闡述了。
現(xiàn)在再來(lái)說(shuō)一下約化的標(biāo)準(zhǔn)概念就不難理解了：如果能找到這樣一個(gè)變化法則，對(duì)任意一個(gè)程序A的輸入，都能按這個(gè)法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說(shuō)，問(wèn)題A可約化為問(wèn)題B。
當(dāng)然，我們所說(shuō)的“可約化”是指的可“多項(xiàng)式地”約化(Polynomial-time Reducible)，即變換輸入的方法是能在多項(xiàng)式的時(shí)間里完成的。約化的過(guò)程只有用多項(xiàng)式的時(shí)間完成才有意義。
好了，從約化的定義中我們看到，一個(gè)問(wèn)題約化為另一個(gè)問(wèn)題，時(shí)間復(fù)雜度增加了，問(wèn)題的應(yīng)用范圍也增大了。通過(guò)對(duì)某些問(wèn)題的不斷約化，我們能夠不斷尋找復(fù)雜度更高，但應(yīng)用范圍更廣的算法來(lái)代替復(fù)雜度雖然低，但只能用于很小的一類問(wèn)題的算法。
再回想前面講的P和NP問(wèn)題，聯(lián)想起約化的傳遞性，自然地，我們會(huì)想問(wèn)，如果不斷地約化上去，不斷找到能“通吃”若干小NP問(wèn)題的一個(gè)稍復(fù)雜的大NP問(wèn)題，那么最后是否有可能找到一個(gè)時(shí)間復(fù)雜度最高，并且能“通吃”所有的 NP問(wèn)題的這樣一個(gè)超級(jí)NP問(wèn)題？
答案居然是肯定的。也就是說(shuō)，存在這樣一個(gè)NP問(wèn)題，所有的NP問(wèn)題都可以約化成它。換句話說(shuō)，只要解決了這個(gè)問(wèn)題，那么所有的NP問(wèn)題都解決了。
這種問(wèn)題的存在難以置信，并且更加不可思議的是，這種問(wèn)題不只一個(gè)，它有很多個(gè)，它是一類問(wèn)題。這一類問(wèn)題就是傳說(shuō)中的NPC 問(wèn)題，也就是NP-完全問(wèn)題。NPC問(wèn)題的出現(xiàn)使整個(gè)NP問(wèn)題的研究得到了飛躍式的發(fā)展。我們有理由相信，NPC問(wèn)題是最復(fù)雜的問(wèn)題。
再次回到全文開(kāi)頭，我們可以看到，人們想表達(dá)一個(gè)問(wèn)題不存在多項(xiàng)式的高效算法時(shí)應(yīng)該說(shuō)它“屬于NPC問(wèn)題”。此時(shí)，我的目的終于達(dá)到了，我已經(jīng)把NP問(wèn)題和NPC問(wèn)題區(qū)別開(kāi)了。
到此為止，本文已經(jīng)寫(xiě)了近5000字了，我佩服你還能看到這里來(lái)，同時(shí)也佩服一下自己能寫(xiě)到這里來(lái)。
NPC問(wèn)題的定義非常簡(jiǎn)單。同時(shí)滿足下面兩個(gè)條件的問(wèn)題就是NPC問(wèn)題。首先，它得是一個(gè)NP問(wèn)題；然后，所有的NP問(wèn)題都可以約化到它。證明一個(gè)問(wèn)題是 NPC問(wèn)題也很簡(jiǎn)單。先證明它至少是一個(gè)NP問(wèn)題，再證明其中一個(gè)已知的NPC問(wèn)題能約化到它（由約化的傳遞性，則NPC問(wèn)題定義的第二條也得以滿足；至于第一個(gè)NPC問(wèn)題是怎么來(lái)的，下文將介紹），這樣就可以說(shuō)它是NPC問(wèn)題了。
既然所有的NP問(wèn)題都能約化成NPC問(wèn)題，那么只要任意一個(gè)NPC問(wèn)題找到了一個(gè)多項(xiàng)式的算法，那么所有的NP問(wèn)題都能用這個(gè)算法解決了，NP也就等于P 了。因此，給NPC找一個(gè)多項(xiàng)式算法太不可思議了。因此，前文才說(shuō)，“正是NPC問(wèn)題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問(wèn)題目前沒(méi)有多項(xiàng)式的有效算法，只能用指數(shù)級(jí)甚至階乘級(jí)復(fù)雜度的搜索。
順便講一下NP-Hard問(wèn)題。NP-Hard問(wèn)題是這樣一種問(wèn)題，它滿足NPC問(wèn)題定義的第二條但不一定要滿足第一條（就是說(shuō)，NP-Hard問(wèn)題要比 NPC問(wèn)題的范圍廣）。NP-Hard問(wèn)題同樣難以找到多項(xiàng)式的算法，但它不列入我們的研究范圍，因?yàn)樗灰欢ㄊ荖P問(wèn)題。即使NPC問(wèn)題發(fā)現(xiàn)了多項(xiàng)式級(jí)的算法，NP-Hard問(wèn)題有可能仍然無(wú)法得到多項(xiàng)式級(jí)的算法。事實(shí)上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問(wèn)題的時(shí)間復(fù)雜度更高從而更難以解決。
不要以為NPC問(wèn)題是一紙空談。NPC問(wèn)題是存在的。確實(shí)有這么一個(gè)非常具體的問(wèn)題屬于NPC問(wèn)題。下文即將介紹它。
下文即將介紹邏輯電路問(wèn)題。這是第一個(gè)NPC問(wèn)題。其它的NPC問(wèn)題都是由這個(gè)問(wèn)題約化而來(lái)的。因此，邏輯電路問(wèn)題是NPC類問(wèn)題的“鼻祖”。
邏輯電路問(wèn)題是指的這樣一個(gè)問(wèn)題：給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為True。
什么叫做邏輯電路呢？一個(gè)邏輯電路由若干個(gè)輸入，一個(gè)輸出，若干“邏輯門”和密密麻麻的線組成。看下面一例，不需要解釋你馬上就明白了。
這是個(gè)較簡(jiǎn)單的邏輯電路，當(dāng)輸入1、輸入2、輸入3分別為True、True、False或False、True、False時(shí)，輸出為True。
有輸出無(wú)論如何都不可能為True的邏輯電路嗎？有。下面就是一個(gè)簡(jiǎn)單的例子。
上面這個(gè)邏輯電路中，無(wú)論輸入是什么，輸出都是False。我們就說(shuō)，這個(gè)邏輯電路不存在使輸出為True的一組輸入。
回到上文，給定一個(gè)邏輯電路，問(wèn)是否存在一種輸入使輸出為True，這即邏輯電路問(wèn)題。
邏輯電路問(wèn)題屬于NPC問(wèn)題。這是有嚴(yán)格證明的。它顯然屬于NP問(wèn)題，并且可以直接證明所有的NP問(wèn)題都可以約化到它（不要以為NP問(wèn)題有無(wú)窮多個(gè)將給證明造成不可逾越的困難）。證明過(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)化為了求出滿足結(jié)果為True的一個(gè)輸入（即一個(gè)可行解）。
有了第一個(gè)NPC問(wèn)題后，一大堆NPC問(wèn)題就出現(xiàn)了，因?yàn)樵僮C明一個(gè)新的NPC問(wèn)題只需要將一個(gè)已知的NPC問(wèn)題約化到它就行了。后來(lái)，Hamilton 回路成了NPC問(wèn)題，TSP問(wèn)題也成了NPC問(wèn)題。現(xiàn)在被證明是NPC問(wèn)題的有很多，任何一個(gè)找到了多項(xiàng)式算法的話所有的NP問(wèn)題都可以完美解決了。因此說(shuō)，正是因?yàn)镹PC問(wèn)題的存在，P=NP變得難以置信。
P=NP問(wèn)題還有許多有趣的東西，有待大家自己進(jìn)一步的挖掘。攀登這個(gè)信息學(xué)的巔峰是我們這一代的終極目標(biāo)。現(xiàn)在我們需要做的，至少是不要把概念弄混淆了。
Python貓注：以上文章寫(xiě)于 2006 年，巧合的是在我讀到這篇文章的兩個(gè)月前，原作者又更新了一篇《16年后重談P和NP問(wèn)題》的文章。你已讀到了這里，說(shuō)明對(duì)此話題很感興趣，為了方便大家閱讀，我把新文也一并分享出來(lái)：
來(lái)源：http://www.matrix67.com/blog/archives/7084#more-7084
2006 年，我在博客（當(dāng)時(shí)還是 MSN Space）上發(fā)了 《什么是 P 問(wèn)題、NP 問(wèn)題和 NPC 問(wèn)題》 一文。這是我高二搞信息學(xué)競(jìng)賽時(shí)隨手寫(xiě)的一些東西，是我的博客中最早的文章之一。今天偶然發(fā)現(xiàn)，這篇現(xiàn)在看了恨不得重寫(xiě)一遍的“科普”竟仍然有比較大的閱讀量。時(shí)間過(guò)得很快。《星際爭(zhēng)霸》（StarCraft）出了續(xù)作，德國(guó)隊(duì) 7 比 1 大勝東道主巴西，《學(xué)徒》（The Apprentice）里的那個(gè)家伙當(dāng)了總統(tǒng)，非典之后竟然出了更大的疫情。現(xiàn)在已經(jīng)是 2022 年了。這 16 年的時(shí)間里，我讀了大學(xué)，出了書(shū)，娶了老婆，養(yǎng)了娃。如果現(xiàn)在的我寫(xiě)一篇同樣話題的科普文章，我會(huì)寫(xiě)成什么樣呢？正好，我的新書(shū)《神機(jī)妙算：一本關(guān)于算法的閑書(shū)》中有一些相關(guān)的內(nèi)容。我從書(shū)里的不同章節(jié)中摘選了一些片段，整理加工了一下，弄出了下面這篇文章，或許能回答剛才的問(wèn)題吧。
有一天，我和老婆去超市大采購(gòu)。和往常一樣，結(jié)完賬之后，我們需要小心謹(jǐn)慎地規(guī)劃把東西放進(jìn)購(gòu)物袋的順序，防止東西被壓壞。這并不是一件容易的事情，尤其是考慮到各個(gè)物體自身的重量和它能承受的重量之間并無(wú)必然聯(lián)系。雞蛋、牛奶非常重，但同時(shí)也很怕壓；毛巾、衛(wèi)生紙都很輕，但卻能承受很大的壓力。
于是，我突然想到了這么一個(gè)問(wèn)題：給定 n 個(gè)物體各自的重量和它能承受的最大重量，判斷出能否把它們疊成一摞，使得所有的物體都不會(huì)被壓壞（一個(gè)物體不會(huì)被壓壞的意思就是，它上面的物體的總重小于等于自己能承受的最大重量）。
事實(shí)證明，這是一個(gè)非常有趣的問(wèn)題——老婆聽(tīng)完這個(gè)問(wèn)題后整日茶飯不思，晚上做夢(mèng)都在念叨著自己構(gòu)造的測(cè)試數(shù)據(jù)。這里，我們不妨給出一組數(shù)據(jù)供大家玩玩。
假設(shè)有 A、B、C、D 四個(gè)物體，其中：物體 A 的自重為 1，最大承重為 9；物體 B 的自重為 5，最大承重為 2；物體 C 的自重為 2，最大承重為 4；物體 D 的自重為 3，最大載重為 12。在這個(gè)例子中，安全的疊放方式是唯一的，你能找出來(lái)嗎？
答案：C 在最上面，其次是 B，其次是 A，最下面是 D。注意，在這個(gè)最優(yōu)方案中，最上面的物體既不是自身重量最小的，也不是承重極限最小的，而是自身重量與承重極限之和最小的。事實(shí)上，最優(yōu)方案中的四個(gè)物體就是按照這個(gè)和的大小排列的！對(duì)于某種疊放方案中的某一個(gè)物體，不妨把它的最大載重減去實(shí)際載重的結(jié)果叫作它的安全系數(shù)。
我們可以證明，這種按自身重量與載重能力之和排序的疊放策略可以讓最危險(xiǎn)的物體盡可能安全，也就是讓最小的那個(gè)安全系數(shù)達(dá)到最大。如果此時(shí)所有物體的安全系數(shù)都是非負(fù)數(shù)，那么我們就相當(dāng)于有了一種滿足要求的疊放方案；如果此時(shí)仍然存在負(fù)的安全系數(shù)，那么我們就永遠(yuǎn)找不到讓所有物體都安全的疊放方案了。
假設(shè)在某種疊放方案中，有兩個(gè)相鄰的物體，上面那個(gè)物體的自身重量和最大載重分別為 W1 和 P1，下面那個(gè)物體的自身重量和最大載重分別為 W2 和 P2。再假設(shè)它倆之上的所有物體的重量之和是 W，這是這兩個(gè)物體都要承擔(dān)的重量。如果 W1 + P1 大于 W2 + P2，那么把這兩個(gè)物體的位置交換一下，會(huì)發(fā)生什么事情呢？原先下面那個(gè)物體的安全系數(shù)為 P2 ? W ? W1，移到上面去之后安全系數(shù)變成了 P2 ? W，這無(wú)疑使它更安全了。原先上面那個(gè)物體的安全系數(shù)為 P1 ? W，移到下面后安全系數(shù)變成了 P1 ? W ? W2，這個(gè)值雖然減小了，但卻仍然大于原先另一個(gè)物體的安全系數(shù) P2 ? W ? W1（這里用到了 W1 + P1 > W2 + P2 的假設(shè)）。因此，交換兩個(gè)物體之后，不但不會(huì)刷新安全系數(shù)的下限，相反有時(shí)還能向上改進(jìn)它。
所以說(shuō)，我們可以不斷地把自身重量與載重能力之和更小的物體換到上面去，反正這不會(huì)讓情況變得更糟。最終得到的最優(yōu)方案，也就與我們前面給出的結(jié)論一致了。
為了解決某類問(wèn)題，我們經(jīng)常需要給出一個(gè)策略，或者說(shuō)一個(gè)方案，或者說(shuō)一個(gè)處理過(guò)程，或者說(shuō)一系列操作規(guī)則，或者更貼切的，一套計(jì)算方法。這就是所謂的“算法” （algorithm）。
讓我們來(lái)總結(jié)一下。我們的問(wèn)題是：給定 n 個(gè)物體各自的重量，以及每個(gè)物體最大可以承受的重量，判斷出能否把它們疊成一摞，使得所有的物體都不會(huì)被壓壞。它的算法則是：按照自身重量與最大承重之和進(jìn)行排序，然后檢驗(yàn)這是否能讓所有物體都不被壓壞，它的答案就決定了整個(gè)問(wèn)題的答案。有了算法后，實(shí)際的計(jì)算過(guò)程一般就會(huì)交給計(jì)算機(jī)來(lái)完成的。程序員的工作，就是編寫(xiě)代碼，把算法告訴計(jì)算機(jī)。
讓計(jì)算機(jī)把每個(gè)物體的自身重量和最大承重加起來(lái)，這好辦。如果有 n 個(gè)物體，那就要算 n 遍加法。給它們排序的時(shí)候，我們要依次做下面這些事情：
這要用 n + 1 + (n ? 1) + 1 + … + 1 + 1=(n2 + 3n) / 2 次操作。物體從上到下該怎么擺，現(xiàn)在就知道了。為了檢驗(yàn)有沒(méi)有東西被壓壞，則需要把物體的重量從上到下累加一遍，邊加邊要和下一個(gè)物體的承重做比較。考慮到最上面的物體不用做檢驗(yàn)，操作次數(shù)姑且就算 2(n ? 1) 吧。這樣的話，整個(gè)算法需要 (n2 + 9n) / 2 ? 2 次操作。當(dāng)然，在編寫(xiě)程序時(shí)，一些細(xì)節(jié)處可能還需要很多額外的操作。不過(guò)，對(duì)于運(yùn)算速度極快的計(jì)算機(jī)來(lái)說(shuō)，這都可以忽略不計(jì)。
計(jì)算機(jī)動(dòng)輒處理成千上萬(wàn)的數(shù)據(jù)，多那么一兩次操作不會(huì)從根本上影響整個(gè)處理過(guò)程的開(kāi)銷。為了評(píng)估處理數(shù)據(jù)的效率，我們更應(yīng)該關(guān)注總操作次數(shù)的“級(jí)別”。我們甚至可以把 (n2 + 3n) / 2 次操作、(n2 + 9n) / 2 ? 2 次操作以及 2n2 + n + 1 次操作、10n2 ? 13n + 500 次操作等等，統(tǒng)統(tǒng)都叫作“操作次數(shù)以 n2 的級(jí)別增長(zhǎng)”，它們都代表著同一個(gè)意思：當(dāng) n 很大的時(shí)候，如果 n 變成了原來(lái)的 k 倍，那么總的開(kāi)銷大致就會(huì)變成原來(lái)的 k2 倍。
1894 年，德國(guó)數(shù)學(xué)家保羅·巴赫曼（Paul Bachmann）提出了一種使用起來(lái)非常方便的“大 O 記號(hào)”（big O notation），用到這里真是再適合不過(guò)了。如果某個(gè)函數(shù) f(n) 的增長(zhǎng)速度不超過(guò) n2 的級(jí)別，那么我們就可以記下 f(n)=O(n2)。因而，隨著 n 的增加，(n2 + 3n) / 2 、(n2 + 9n) / 2 ? 2 、2n2 + n + 1 、10n2 ? 13n + 500 的增長(zhǎng)速度都可以用 O(n2) 來(lái)表示。類似地，n3 / 10、(n3 + 3n) / 2、10n3 ? 6n2 + 100 則都相當(dāng)于 O(n3)。
完成剛才那個(gè)算法需要的操作次數(shù)是 O(n2) 級(jí)別的。假設(shè)每次操作耗時(shí)相同，那么運(yùn)行這個(gè)算法所需要的時(shí)間也應(yīng)該是 O(n2) 級(jí)別的。更專業(yè)的說(shuō)法則是，整個(gè)算法的“時(shí)間復(fù)雜度”（time complexity）為 O(n2)。
1985 年由英特爾公司推出的 80386 芯片每秒鐘可以執(zhí)行 200 萬(wàn)個(gè)指令，1999 年的英特爾奔騰 III 處理器每秒鐘可以執(zhí)行 20 億個(gè)指令，2012 年的英特爾酷睿 i7 處理器每秒則可以執(zhí)行 1000 億個(gè)以上的指令。
不妨假設(shè)，當(dāng) n=10 的時(shí)候，借助上述算法，計(jì)算機(jī)只需要 0.1 毫秒就能得到答案。算法的時(shí)間復(fù)雜度為 O(n2)，說(shuō)明當(dāng) n 增加到原來(lái)的 100 倍時(shí)，運(yùn)行完成所需的時(shí)間會(huì)增加到原來(lái)的 10000 倍。因此，如果 n 變成了 1000 時(shí)，計(jì)算機(jī)也只需要 1 秒就能得到答案。即使 n 增加到了 100000，計(jì)算機(jī)也只需要 10000 秒就能得到答案，這大約相當(dāng)于 2 個(gè)小時(shí)又 47 分鐘。
其實(shí)，為了判斷出這些物體能否安全疊放，我們似乎完全不必如此煞費(fèi)心機(jī)。我們還有一個(gè)更基本的方法：枚舉所有可能的疊放順序，看看有沒(méi)有滿足要求的方案。n 個(gè)物體一共會(huì)產(chǎn)生 n! 種不同的疊放順序，每次檢驗(yàn)都需要耗費(fèi) O(n) 的時(shí)間。所以，為了得到答案，最壞情況下的時(shí)間復(fù)雜度為 O(n · n!)。
那么，我們?yōu)槭裁床徊捎眠@種粗暴豪爽的算法呢？主要原因大概就是，這種算法的時(shí)間復(fù)雜度有些太高。但是，既然計(jì)算機(jī)的運(yùn)算速度如此之快，O(n · n!) 的時(shí)間復(fù)雜度想必也不在話下吧？讓我們來(lái)看一看。仍然假設(shè) n=10 的時(shí)候，計(jì)算機(jī)只需要 0.1 毫秒就能得到答案。令人吃驚的是，若真的以 O(n · n!) 的級(jí)別增長(zhǎng)，到了 n=15 的時(shí)候，完成算法全過(guò)程需要的時(shí)間就已經(jīng)增加到了 54 秒。當(dāng) n=20 時(shí)，算法全過(guò)程耗時(shí) 1.34 億秒，這相當(dāng)于 1551 天，也就是 4.25 年。當(dāng) n=30 時(shí)，算法全過(guò)程耗時(shí) 700 萬(wàn)億年，而目前的資料顯示，宇宙大爆炸也不過(guò)是在 137 億年以前。如果 n=100 的話，計(jì)算機(jī)需要不分晝夜地工作 8.15 × 10140 年才能得到答案。根據(jù)目前的宇宙學(xué)理論，到了那個(gè)時(shí)候，整個(gè)宇宙早已一片死寂。
為什么 O(n2) 和 O(n · n!) 的差異那么大呢？原因就是，前者畢竟屬于多項(xiàng)式級(jí)的增長(zhǎng)，后者則已經(jīng)超過(guò)了指數(shù)級(jí)的增長(zhǎng)。
指數(shù)級(jí)的增長(zhǎng)真的非常可怕，雖然 n 較小的時(shí)候看上去似乎很平常，但它很快就會(huì)超出你的想象，完全處于失控狀態(tài)。一張紙對(duì)折一次會(huì)變成 2 層，再對(duì)折一次會(huì)變成 4 層……如此下去，每對(duì)折一次這個(gè)數(shù)目便會(huì)翻一倍。因此，一張紙對(duì)折了 n 次后，你就能得到 2n 層紙。當(dāng) n=5 時(shí)，紙張層數(shù) 2n=32；當(dāng) n=10 時(shí)，紙張層數(shù)瞬間變成了 1024；當(dāng) n=30 時(shí)，你面前將出現(xiàn) 230=1 073 741 824 層紙！一張紙的厚度大約是 0.1 毫米，這十億多張紙疊加在一起，也就有 10 萬(wàn)多米。卡門線（Kármán line）位于海拔 100 千米處，是國(guó)際標(biāo)準(zhǔn)規(guī)定的外太空與地球大氣層的界線。這表明，把一張紙對(duì)折 30 次以后，其總高度將會(huì)超出地球的大氣層，直達(dá)外太空。
波斯史詩(shī)《王書(shū)》記載的故事也形象地道出了指數(shù)級(jí)增長(zhǎng)的猛烈程度。一位智者發(fā)明了國(guó)際象棋，國(guó)王想要獎(jiǎng)賞他，問(wèn)他想要什么。智者說(shuō)：“在這個(gè)棋盤(pán)的第一個(gè)格子里放上一顆大米，第二個(gè)格子里放上兩顆大米，第三個(gè)格子里放上四顆大米，以此類推，每個(gè)格子里的大米數(shù)都是前一個(gè)格子的兩倍。所有 64 個(gè)格子里的大米就是我想要的獎(jiǎng)賞了。”國(guó)王覺(jué)得這很容易辦到，便欣然同意了。殊不知，哪怕只看第 64 個(gè)格子里的大米，就已經(jīng)有 263 ≈ 9.22 × 1019 顆了。如果把這些大米分給當(dāng)時(shí)世界上的每個(gè)人，那么每一個(gè)人都會(huì)得到上千噸大米。國(guó)際象棋的棋盤(pán)里幸好只有 64 個(gè)格子。如果國(guó)際象棋的棋盤(pán)里有 300 個(gè)格子，里面的大米顆數(shù)就會(huì)超過(guò)全宇宙的原子總數(shù)了。
因而，在計(jì)算機(jī)算法領(lǐng)域，我們有一個(gè)最基本的假設(shè)：所有實(shí)用的、快速的、高效的算法，其時(shí)間復(fù)雜度都應(yīng)該是多項(xiàng)式級(jí)別的。因此，在為計(jì)算機(jī)編寫(xiě)程序解決實(shí)際問(wèn)題時(shí)，我們往往希望算法的時(shí)間復(fù)雜度是多項(xiàng)式級(jí)別的。
這里的“問(wèn)題”一詞太過(guò)寬泛，可能會(huì)帶來(lái)很多麻煩，因而我們規(guī)定，接下來(lái)所說(shuō)的問(wèn)題都是指的“判定性問(wèn)題”（decision problem），即那些給定某些數(shù)據(jù)之后，要求回答“是”或者“否”的問(wèn)題。
在復(fù)雜度理論中，如果某個(gè)判定性問(wèn)題可以用計(jì)算機(jī)在多項(xiàng)式級(jí)別的時(shí)間內(nèi)解出，我們就說(shuō)這個(gè)問(wèn)題是一個(gè) P 問(wèn)題，或者說(shuō)它屬于集合 P。這里，P 是“多項(xiàng)式”的英文單詞 polynomial 的第一個(gè)字母。之前那個(gè)疊放東西的問(wèn)題，就是一個(gè) P 問(wèn)題。
歷史上至少有過(guò)兩個(gè)問(wèn)題，它們看起來(lái)非常困難，非常不像 P 問(wèn)題，但在人們的不懈努力之下，最終還是成功地加入了 P 問(wèn)題的大家庭。其中一個(gè)是線性規(guī)劃（linear programming），它是一種起源于二戰(zhàn)時(shí)期的運(yùn)籌學(xué)模型。1947 年，喬治·丹齊格（George Dantzig）提出了一種非常漂亮的算法叫作“單純形法”（simplex algorithm），它在隨機(jī)數(shù)據(jù)中的表現(xiàn)極為不錯(cuò)，但在最壞情況下卻需要耗費(fèi)指數(shù)級(jí)的時(shí)間。因此，很長(zhǎng)一段時(shí)間，人們都在懷疑，線性規(guī)劃是否有多項(xiàng)式級(jí)的算法。直到 1979 年，人們才迎來(lái)了線性規(guī)劃的第一個(gè)多項(xiàng)式級(jí)的算法，它是由前蘇聯(lián)數(shù)學(xué)家列昂尼德·哈奇揚(yáng)（Leonid Khachiyan）提出的。
另外一個(gè)問(wèn)題則是質(zhì)數(shù)判定問(wèn)題（primality test）：判斷一個(gè)正整數(shù)是否是質(zhì)數(shù)（prime），或者說(shuō)判斷一個(gè)正整數(shù)是不是無(wú)法分成兩個(gè)更小的正整數(shù)之積。人們?cè)?jīng)提出過(guò)各種質(zhì)數(shù)判定的多項(xiàng)式級(jí)算法，但它們要么是基于概率的，要么是基于某些假設(shè)的，要么是有一定適用范圍的。2002 年，來(lái)自印度理工學(xué)院坎普爾分校的阿格拉瓦爾（M. Agrawal）、卡亞勒（N. Kayal）和薩克斯泰納（N. Saxena）發(fā)表了一篇重要的論文《PRIMES is in P》，給出了第一個(gè)確定性的、時(shí)間復(fù)雜度為多項(xiàng)式級(jí)別的質(zhì)數(shù)判定算法，質(zhì)數(shù)判定問(wèn)題便也歸入了 P 問(wèn)題的集合。
同時(shí)，我們也有很多游離于集合 P 之外的問(wèn)題。互聯(lián)網(wǎng)安全高度依賴于一種叫作 RSA 算法的加密體系，里面用到了非常犀利的一點(diǎn)：在整數(shù)世界里，合成與分解的難度是不對(duì)等的。任意選兩個(gè)比較大的質(zhì)數(shù)，比如 19 394 489 和 27 687 937。我們能夠很容易計(jì)算出它倆相乘的結(jié)果，它等于 536 993 389 579 193；但是，如果反過(guò)來(lái)問(wèn)你，536 993 389 579 193 可以分解成哪兩個(gè)質(zhì)數(shù)的乘積，這卻非常難以迅速作答。把一個(gè)大整數(shù)分解成若干個(gè)質(zhì)數(shù)之積，這就是著名的“整數(shù)分解問(wèn)題”（integer factorization problem）。目前，人們還沒(méi)有找到一種快速有效的整數(shù)分解算法。也就是說(shuō)，目前人們還不知道整數(shù)分解問(wèn)題是否屬于 P。（這里我們指的也是整數(shù)分解問(wèn)題的判定性版本，即給定一個(gè)正整數(shù) N 和一個(gè)小于 N 的正整數(shù) M，判斷出 N 是否能被某個(gè)不超過(guò) M 的數(shù)整除。）人們猜測(cè)，整數(shù)分解很可能不屬于 P。這正是 RSA 算法目前足夠安全的原因。
另一個(gè)著名的問(wèn)題叫作“子集和問(wèn)題”（subset sum problem）：給定一個(gè)整數(shù)集合 S 以及一個(gè)大整數(shù) M，判斷出能否在 S 里選出一些數(shù)，使得它們的和正好為 M？比方說(shuō)，假設(shè)集合 S 為
{38, 71, 45, 86, 68, 65, 82, 89, 84, 85, 91, 8}
并且大整數(shù) M=277，那么你就需要判斷出，能否在上面這一行數(shù)里選出若干個(gè)數(shù)，使得它們相加之后正好等于 277。為了解決這類問(wèn)題，其中一種算法就是，枚舉所有可能的選數(shù)方案，看看有沒(méi)有滿足要求的方案。如果我們用 n 來(lái)表示集合里的元素個(gè)數(shù)，那么所有可能的選數(shù)方案就有 O(2n) 種，檢驗(yàn)每一種方案都需要花費(fèi) O(n) 的時(shí)間，因而整個(gè)算法的時(shí)間復(fù)雜度為 O(n · 2n)。雖然人們已經(jīng)找到了時(shí)間復(fù)雜度更低的算法，但沒(méi)有一種算法的時(shí)間復(fù)雜度是多項(xiàng)式級(jí)別的。人們猜測(cè)，子集和問(wèn)題很可能也不屬于 P。
美國(guó)計(jì)算機(jī)科學(xué)家杰克·埃德蒙茲（Jack Edmonds）在 1964 年的一篇討論某個(gè)矩陣問(wèn)題的論文中，也提到了類似于 P 問(wèn)題的概念：“當(dāng)然，給定一個(gè)矩陣后，考慮所有可能的染色方案，我們一定能碰上一個(gè)符合要求的剖分，但這種方法所需要的工作量大得驚人。我們要尋找一種算法，使得隨著矩陣大小的增加，工作量?jī)H僅是呈代數(shù)式地上漲……和大多數(shù)組合問(wèn)題一樣，找出一個(gè)有限的算法很容易，找出一個(gè)滿足上述條件的，從而能在實(shí)際中運(yùn)用的算法，就不那么容易了。”
接下來(lái)，埃德蒙茲模模糊糊地觸碰到了一個(gè)新的概念：“給定一個(gè)矩陣，它的各列最少能被剖分成多少個(gè)獨(dú)立集？我們?cè)囍页鲆粋€(gè)好的刻畫(huà)方式。至于什么叫作‘好的刻畫(huà)’，我們則采用‘絕對(duì)主管原則’。一個(gè)好的刻畫(huà)，應(yīng)該能透露出矩陣的某些信息，使得某個(gè)主管能夠在助手找到一個(gè)最小的剖分方案之后，輕易地驗(yàn)證出這確實(shí)是最小的剖分方案。有了一個(gè)好的刻畫(huà)，并不意味著就有一個(gè)好的算法。助手很可能還是得拼死拼活，才能找到那個(gè)剖分方案。”
埃德蒙茲后面所說(shuō)的，不是設(shè)計(jì)一種多項(xiàng)式級(jí)的算法來(lái)尋找答案，而是設(shè)計(jì)一種多項(xiàng)式級(jí)的算法來(lái)驗(yàn)證答案的正確性。對(duì)于很多問(wèn)題，這件事情是很好辦的。為了向人們展示出確實(shí)有可能讓所有的物體都不被壓壞，我們只需要給出一種滿足要求的物體疊放順序，并讓計(jì)算機(jī)用 O(n) 的時(shí)間驗(yàn)證它的確滿足要求即可。為了向人們展示出集合中的某些數(shù)加起來(lái)能得出 277，我們只需要提供一種選數(shù)的方法，并讓計(jì)算機(jī)用 O(n) 的時(shí)間求和檢驗(yàn)。
對(duì)于有些問(wèn)題來(lái)說(shuō)，如果答案是肯定的，我們可能并沒(méi)有一種非常明顯的高效方法來(lái)檢驗(yàn)這一點(diǎn)。不過(guò)，很容易看出，找出一個(gè)多項(xiàng)式級(jí)的答案驗(yàn)核算法，再怎么也比找出一個(gè)多項(xiàng)式級(jí)的答案獲取算法更容易。很多看上去非常困難的問(wèn)題，都是先找到多項(xiàng)式級(jí)的答案驗(yàn)核算法，再找到多項(xiàng)式級(jí)的答案獲取算法的。
一個(gè)經(jīng)典的例子就是質(zhì)數(shù)判定問(wèn)題。如果某個(gè)數(shù)確實(shí)是一個(gè)質(zhì)數(shù)，你怎樣才能在多項(xiàng)式級(jí)的時(shí)間里證明這一點(diǎn)？1975 年，沃恩·普拉特（Vaughan Pratt）在《每個(gè)質(zhì)數(shù)都有一份簡(jiǎn)短的證明書(shū)》（Every Prime Has a Succinct Certificate）一文中給出了一種這樣的方法，無(wú)疑推動(dòng)了質(zhì)數(shù)判定算法的發(fā)展。
還有些問(wèn)題是如此之難，以至于目前人們不但沒(méi)有找到多項(xiàng)式級(jí)的答案獲取算法，而且還不知道是否存在多項(xiàng)式級(jí)的答案驗(yàn)核算法。比如經(jīng)典的“第 K 大子集問(wèn)題”（Kth largest subset problem）：給定一個(gè)含有 n 個(gè)整數(shù)的集合 S，一個(gè)大整數(shù) M，以及一個(gè)不超過(guò) 2n 的整數(shù) K，判斷出是否存在至少 K 個(gè)不同的子集，使得每個(gè)子集里的元素之和都不超過(guò) M？如果答案是肯定的，一個(gè)很容易想到的驗(yàn)證方法便是，把所有滿足要求的 K 個(gè)子集都列出來(lái)，并交由計(jì)算機(jī)審核。只可惜，子集的數(shù)目是指數(shù)級(jí)的，因而審核工作也將會(huì)花費(fèi)指數(shù)級(jí)的時(shí)間。人們猜測(cè)，第 K 大子集問(wèn)題很可能沒(méi)有多項(xiàng)式級(jí)別的檢驗(yàn)方法。
在復(fù)雜度理論中，一個(gè)問(wèn)題有沒(méi)有高效的答案驗(yàn)核算法，也是一個(gè)非常重要的研究課題。對(duì)于一個(gè)判定性問(wèn)題，如果存在一個(gè)多項(xiàng)式級(jí)的算法，使得每次遇到答案應(yīng)為“是”的時(shí)候，我們都能向這個(gè)算法輸入一段適當(dāng)?shù)摹白C據(jù)”，讓算法運(yùn)行完畢后就能確信答案確實(shí)為“是”，我們就說(shuō)這個(gè)問(wèn)題是一個(gè) NP 問(wèn)題，或者說(shuō)它屬于集合 NP。為了解釋“NP 問(wèn)題”這個(gè)名字的來(lái)由，我們不得不提到 NP 問(wèn)題的另一個(gè)等價(jià)定義：可以在具備隨機(jī)功能的機(jī)器上用多項(xiàng)式級(jí)的時(shí)間解決的問(wèn)題。
如果允許計(jì)算機(jī)的指令發(fā)生沖突，比如指令集里面既有 “如果遇到情況 A，則執(zhí)行操作 B”，又有 “如果遇到情況 A，則執(zhí)行操作 C”，我們就認(rèn)為這樣的計(jì)算機(jī)具備了隨機(jī)的功能。這種新型的計(jì)算機(jī)就叫作“非確定型”（nondeterministic）機(jī)器。機(jī)器一旦遇到了矛盾糾結(jié)之處，就隨機(jī)選擇一條指令執(zhí)行。你可以把機(jī)器面對(duì)的每一次隨機(jī)選擇都想象成是一個(gè)通向各個(gè)平行世界的岔路口，因而整臺(tái)機(jī)器可以同時(shí)試遍所有的分支，自動(dòng)探尋所有的可能。如果你看過(guò)尼古拉斯·凱奇（Nicolas Cage）主演的電影《預(yù)見(jiàn)未來(lái)》（Next），你或許會(huì)對(duì)這一幕非常熟悉。只要在任意一個(gè)分支里機(jī)器回答了“是”，那么整臺(tái)機(jī)器也就算作回答了“是”。
在如此強(qiáng)大的機(jī)器上，很多問(wèn)題都不是問(wèn)題了。為了判斷出能否讓所有的物體都不被壓壞，我們只需要讓機(jī)器每次都從剩余物體中隨便選一個(gè)放，看看由此產(chǎn)生的 n! 種放法里是否有哪種放法符合要求。為了判斷出集合中是否有某些數(shù)加起來(lái)等于 277，我們只需要讓機(jī)器隨機(jī)決定每個(gè)數(shù)該選還是不選，最后看看有沒(méi)有哪次選出來(lái)的數(shù)之和正好是 277。
事實(shí)上，在非確定型計(jì)算機(jī)上可以用多項(xiàng)式級(jí)的時(shí)間獲取到答案的問(wèn)題，正是那些在確定型計(jì)算機(jī)上可以用多項(xiàng)式級(jí)的時(shí)間驗(yàn)核答案的問(wèn)題，原因很簡(jiǎn)單：如果一個(gè)問(wèn)題可以在非確定型計(jì)算機(jī)上獲解，找到解的那個(gè)分支沿途做出的選擇就成了展示答案正確性的最有力證據(jù)；反之，如果我們能在確定型計(jì)算機(jī)上驗(yàn)核出答案確實(shí)為“是”，我們便可以在非確定型計(jì)算機(jī)上隨機(jī)產(chǎn)生驗(yàn)核所需的證據(jù)，看看在所有可能的證據(jù)當(dāng)中會(huì)不會(huì)出現(xiàn)一條真的能通過(guò)驗(yàn)核的證據(jù)。“非確定型”的英文單詞是 nondeterministic，它的第一個(gè)字母是 N；“多項(xiàng)式”的英文單詞是 polynomial，它的第一個(gè)字母是 P。NP 問(wèn)題便如此得名。
容易想到，所有的 P 問(wèn)題一定都是 NP 問(wèn)題，但反過(guò)來(lái)就不好說(shuō)了。例如，子集和問(wèn)題是屬于 NP 的。然而，之前我們就曾經(jīng)討論過(guò)，人們不但沒(méi)有找到子集和問(wèn)題的多項(xiàng)式級(jí)解法，而且也相信子集和問(wèn)題恐怕根本就沒(méi)有多項(xiàng)式級(jí)的解法。因而，子集和問(wèn)題很可能屬于這么一種類型的問(wèn)題：它屬于集合 NP，卻不屬于集合 P。
1971 年，史提芬·古克（Stephen Cook）發(fā)表了計(jì)算機(jī)科學(xué)領(lǐng)域最重要的論文之一——《定理證明過(guò)程的復(fù)雜性》（The Complexity of Theorem-Proving Procedures）。在這篇論文里，史提芬·古克提出了一個(gè)著名的問(wèn)題：P 等于 NP 嗎？
如果非要用一句最簡(jiǎn)單、最直觀的話來(lái)描述這個(gè)問(wèn)題，那就是：能高效地檢驗(yàn)解的正確性，是否就意味著能高效地找出一個(gè)解？數(shù)十年來(lái)，無(wú)數(shù)的學(xué)者向這個(gè)問(wèn)題發(fā)起了無(wú)數(shù)次進(jìn)攻。根據(jù)格哈德·韋金格（Gerhard Woeginger）的統(tǒng)計(jì)，僅從 1996 年算起，就有 100 余人聲稱解決了這個(gè)問(wèn)題，其中 55 人聲稱 P 是等于 NP 的，另外 45 人聲稱 P 是不等于 NP 的，還有若干人聲稱這個(gè)問(wèn)題理論上不可能被解決。
但不出所料的是，所有這些“證明”都是錯(cuò)誤的。目前為止，既沒(méi)有人真正地證明了 P=NP，也沒(méi)有人真正地證明了 P ≠ NP，也沒(méi)有人真正地證明了這個(gè)問(wèn)題的不可解性。這個(gè)問(wèn)題毫無(wú)疑問(wèn)地成為了計(jì)算機(jī)科學(xué)領(lǐng)域最大的未解之謎。
在 2000 年美國(guó)克雷數(shù)學(xué)研究所（Clay Mathematics Institute）公布的千禧年七大數(shù)學(xué)難題（Millennium Prize Problems）中，P 和 NP 問(wèn)題排在了第一位。第一個(gè)解決該問(wèn)題的人將會(huì)獲得一百萬(wàn)美元的獎(jiǎng)金。
讓我們來(lái)看一下，科學(xué)家們都是怎么看 P 和 NP 問(wèn)題的吧。英國(guó)數(shù)學(xué)家、生命游戲（Game of Life）的發(fā)明者約翰·康威（John Conway）認(rèn)為，P 是不等于 NP 的，并且到了 21 世紀(jì) 30 年代就會(huì)有人證明這一點(diǎn)。他說(shuō)道：“我覺(jué)得這本來(lái)不應(yīng)該是什么難題，只是這個(gè)理論來(lái)得太遲，我們還沒(méi)有弄出任何解決問(wèn)題的工具。”
美國(guó)計(jì)算機(jī)科學(xué)家、1985 年圖靈獎(jiǎng)獲得者理查德·卡普（Richard Karp）也認(rèn)為，P 是不等于 NP 的。他說(shuō)：“我認(rèn)為傳統(tǒng)的證明方法是遠(yuǎn)遠(yuǎn)不夠的，解決這個(gè)問(wèn)題需要一種絕對(duì)新奇的手段。直覺(jué)告訴我，這個(gè)問(wèn)題最終會(huì)由一位不被傳統(tǒng)思想束縛的年輕科學(xué)家解決掉。”
美國(guó)計(jì)算機(jī)科學(xué)家、《自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算導(dǎo)論》（Introduction to Automata Theory, Languages and Computation）的作者杰夫瑞·厄爾曼（Jeffrey Ullman）同樣相信 P 不等于 NP。他說(shuō)：“我認(rèn)為這個(gè)問(wèn)題和那些困擾人類上百年的數(shù)學(xué)難題有得一拼，比如四色定理（four color theorem）。所以我猜測(cè)，解決這個(gè)問(wèn)題至少還要 100 年。我敢肯定，解決問(wèn)題所需的工具至今仍未出現(xiàn)，甚至連這種工具的名字都還沒(méi)有出現(xiàn)。但別忘了，那些最偉大的數(shù)學(xué)難題剛被提出來(lái)的 30 年里，所面對(duì)的也是這樣的情況。”
你或許會(huì)注意到，大家似乎都傾向于認(rèn)為 P ≠ NP 。事實(shí)上，根據(jù)威廉·加薩奇（William Gasarch）的調(diào)查，超過(guò)八成的學(xué)者都認(rèn)為 P ≠ NP。這至少有兩個(gè)主要的原因。首先，證明 P=NP 看上去比證明 P ≠ NP 更容易，但即使這樣，目前仍然沒(méi)有任何跡象表明 P=NP。為了證明 P=NP，我們只需要構(gòu)造一種可以適用于一切 NP 問(wèn)題的超級(jí)萬(wàn)能的多項(xiàng)式級(jí)求解算法。在那篇?jiǎng)潟r(shí)代的論文里，史提芬·古克證明了一個(gè)頗有些出人意料的結(jié)論，讓 P=NP 的構(gòu)造性證明看起來(lái)更加唾手可得。給你一堆正整數(shù)，問(wèn)能否把它們分成總和相等的兩堆，這個(gè)問(wèn)題叫作“分區(qū)問(wèn)題”（partition problem）。
容易看出，分區(qū)問(wèn)題可以轉(zhuǎn)化為子集和問(wèn)題的一個(gè)特例，你只需要把子集和問(wèn)題中的目標(biāo)設(shè)定成所有數(shù)之和的一半即可。這說(shuō)明，子集和問(wèn)題是一個(gè)比分區(qū)問(wèn)題更一般的“大問(wèn)題”，它可以用來(lái)解決包括分區(qū)問(wèn)題在內(nèi)的很多“小問(wèn)題”。史提芬·古克則證明了，在 NP 問(wèn)題的集合里，存在至少一個(gè)最“大”的問(wèn)題，它的表達(dá)能力如此之強(qiáng)，以至于一切 NP 問(wèn)題都可以在多項(xiàng)式的時(shí)間里變成這個(gè)問(wèn)題的一種特例。很容易想到，如果這樣的“終極 NP 問(wèn)題”有了多項(xiàng)式級(jí)的求解算法，所有的 NP 問(wèn)題都將擁有多項(xiàng)式級(jí)的求解算法。這樣的問(wèn)題就叫作“NP 完全問(wèn)題”（NP-complete problem）。在論文中，史提芬·古克構(gòu)造出了一個(gè)具體的 NP 完全問(wèn)題，它涉及到了很多計(jì)算機(jī)底層的邏輯運(yùn)算，能蘊(yùn)含所有的 NP 問(wèn)題其實(shí)也不是非常奇怪的事。
后來(lái)，人們還找到了很多其他的 NP 完全問(wèn)題。1972 年，理查德·卡普發(fā)表了《組合問(wèn)題中的可歸約性》（Reducibility among Combinatorial Problems）一文。這是復(fù)雜度理論當(dāng)中又一篇里程碑式的論文，“P 問(wèn)題”、“NP 問(wèn)題”、“NP 完全問(wèn)題”等術(shù)語(yǔ)就在這里誕生。
在這篇論文里，理查德·卡普列出了 21 個(gè) NP 完全問(wèn)題，其中不乏一些看起來(lái)很“正常”、很“自然”的問(wèn)題，剛才提到的子集和問(wèn)題就是其中之一。1979 年，邁克爾·加里（Michael Garey）和戴維·約翰遜（David Johnson）合作出版了第一本與 NP 完全問(wèn)題理論相關(guān)的教材——《計(jì)算機(jī)和難解性：NP 完全性理論導(dǎo)引》（Computers and Intractability: A Guide to the Theory of NP-Completeness）。該書(shū)的附錄中列出了超過(guò) 300 個(gè) NP 完全問(wèn)題，這一共用去了 100 頁(yè)的篇幅，幾乎占了整本書(shū)的三分之一。
如果這些 NP 完全問(wèn)題當(dāng)中的任何一個(gè)問(wèn)題擁有了多項(xiàng)式級(jí)的求解算法，所有的 NP 問(wèn)題都將自動(dòng)地獲得多項(xiàng)式級(jí)的求解算法，P 也就等于 NP 了。然而，這么多年過(guò)去了，沒(méi)有任何人找到任何一個(gè) NP 完全問(wèn)題的任何一種多項(xiàng)式解法。這讓人們不得不轉(zhuǎn)而相信，P 是不等于 NP 的。
人們相信 P ≠ NP 的另一個(gè)原因是，這個(gè)假設(shè)經(jīng)受住了實(shí)踐的考驗(yàn)。工業(yè)與生活中的諸多方面都依賴于 P ≠ NP 的假設(shè)。如果哪一天科學(xué)家們證明了 P=NP，尋找一個(gè)解和驗(yàn)證一個(gè)解變得同樣容易，這個(gè)世界將會(huì)大不一樣。1995 年，魯塞爾·因帕利亞佐（Russell Impagliazzo）對(duì)此做了一番生動(dòng)描述。
首先，各種各樣的 NP 問(wèn)題，尤其是那些最為困難的 NP 完全問(wèn)題，都將全部獲得多項(xiàng)式級(jí)的解法。工業(yè)上、管理上的幾乎所有最優(yōu)化問(wèn)題都立即有了高效的求解方案。事實(shí)上，我們甚至不需要編程告訴計(jì)算機(jī)應(yīng)該怎樣求解問(wèn)題，我們只需要編程告訴計(jì)算機(jī)我們想要什么樣的解，編譯器將會(huì)自動(dòng)為我們做好一個(gè)高效的求解系統(tǒng)。
其次，很多人工智能問(wèn)題也迎刃而解了。比方說(shuō)，為了讓計(jì)算機(jī)具備中文處理能力，我們可以準(zhǔn)備一個(gè)訓(xùn)練集，里面包含一大批句子樣本，每個(gè)句子都帶有“符合語(yǔ)法”、“不符合語(yǔ)法”這兩種標(biāo)記之一。接下來(lái)，我們要求計(jì)算機(jī)構(gòu)造一個(gè)代碼長(zhǎng)度最短的程序，使得將這些語(yǔ)句輸入這個(gè)程序后，程序能正確得出它們是否符合語(yǔ)法。顯然，這個(gè)最優(yōu)化問(wèn)題本身是一個(gè) NP 問(wèn)題（這里有個(gè)前提，即這樣的程序是存在的，并且是多項(xiàng)式級(jí)別的），因此計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)找到這個(gè)最簡(jiǎn)程序。
根據(jù)奧卡姆剃刀原理（Occam’s razor），我們有理由相信，這個(gè)程序背后的算法也就是人類頭腦中正在使用的算法，因此它能夠適用于所給材料之外的其他語(yǔ)句，并具有自我學(xué)習(xí)的功能。數(shù)學(xué)家的很多工作也可以完全交給計(jì)算機(jī)來(lái)處理。尋找一個(gè)反例和驗(yàn)證一個(gè)反例變得同樣簡(jiǎn)單，各種錯(cuò)誤的猜想都將很快被推翻。事實(shí)上，尋找一個(gè)數(shù)學(xué)證明和驗(yàn)證一個(gè)證明的正確性也變得同樣簡(jiǎn)單，因此各種正確的命題也能夠很快找到一個(gè)最簡(jiǎn)的證明。
最后，不要高興得太早——P=NP 的世界也將會(huì)是一個(gè)極不安全的世界。電子簽名技術(shù)不再有效，因?yàn)閭卧煲欢魏戏ǖ暮灻兊煤万?yàn)證簽名是否合法一樣輕松。RSA 算法也不再有效，因?yàn)閷ふ乙粋€(gè)質(zhì)因數(shù)變得和判斷整除性一樣簡(jiǎn)單。事實(shí)上，發(fā)明任何新的密碼算法都是徒勞——計(jì)算機(jī)可以根據(jù)一大批明文密文樣本推算出生成密文的算法（只要這個(gè)算法本身是多項(xiàng)式的）。
更進(jìn)一步，在網(wǎng)絡(luò)上，你再也沒(méi)法把人和人區(qū)別開(kāi)來(lái)，甚至沒(méi)法把人和計(jì)算機(jī)區(qū)別開(kāi)來(lái)。計(jì)算機(jī)不僅能輕易通過(guò)圖靈測(cè)試（Turing test），還能精確地模仿某一個(gè)特定的人。如果你能把某個(gè)人的網(wǎng)絡(luò)聊天記錄全部搜集起來(lái)，把這個(gè)人和網(wǎng)友們的對(duì)話全部遞交給計(jì)算機(jī)，計(jì)算機(jī)將會(huì)很快學(xué)會(huì)如何模仿這個(gè)人。網(wǎng)絡(luò)的身份鑒定必須要借助物理手段。即使是在科幻故事中，這樣的設(shè)定也相當(dāng)瘋狂，可見(jiàn) P=NP 有多不可能了。
雖然種種證據(jù)表明 P ≠ NP，但我們?nèi)匀粺o(wú)法排除 P=NP 的可能性。其實(shí)，如果 P 真的等于 NP，但時(shí)間復(fù)雜度的次數(shù)非常大非常大非常大，密碼學(xué)的根基仍然不太可能動(dòng)搖，我們的世界仍然不太可能大變。被譽(yù)為“算法分析之父”的計(jì)算機(jī)科學(xué)大師高德納（Donald Knuth）還提出了這樣一種可能：未來(lái)有人利用反證法證明了 P=NP，于是我們知道了所有 NP 問(wèn)題都有多項(xiàng)式級(jí)的算法，但算法的時(shí)間復(fù)雜度究竟是多少，我們?nèi)匀灰粺o(wú)所知！
對(duì)于很多人來(lái)說(shuō)，找不到任何一個(gè) NP 完全問(wèn)題的多項(xiàng)式級(jí)算法，同樣不應(yīng)成為質(zhì)疑 P=NP 的理由。荻原光德（Mitsunori Ogihara）認(rèn)為，最終人們或許會(huì)成功地證明 P=NP，但這絕不是一兩個(gè)人死死糾纏某一個(gè) NP 完全問(wèn)題就能辦到的。對(duì)此，他做了更為細(xì)致的想象。
XX 世紀(jì)后期，一份非常簡(jiǎn)略的、從未發(fā)表過(guò)的草稿，無(wú)意中開(kāi)辟了解決 P 和 NP 問(wèn)題的道路。這份草稿出自 20 世紀(jì)的一位數(shù)學(xué)天才 FOO 之手，當(dāng)時(shí)他正在嘗試著建立某種代數(shù)結(jié)構(gòu)的新理論。顯然，F(xiàn)OO 很快放棄了這個(gè)想法，并且今后從未重新拾起這個(gè)課題。這份草稿一直卡在 FOO 的臥室地板的縫隙里，在后來(lái)的一次舊房翻新工程中才被工人們發(fā)現(xiàn)。由于草稿太過(guò)簡(jiǎn)略，因而當(dāng)時(shí)并未引起太多關(guān)注。然而，幾十年后，一群數(shù)學(xué)家發(fā)現(xiàn)，如果草稿上面的某個(gè)假設(shè)的某個(gè)變形成立，將會(huì)推出很多有意思的東西。雖然這不是 FOO 本來(lái)要做的假設(shè)，但它還是被人們稱作“FOO 假設(shè)”，以紀(jì)念這位數(shù)學(xué)天才。
大約 100 年后，一群計(jì)算機(jī)科學(xué)家發(fā)現(xiàn)，如果 FOO 假設(shè)成立，那么某個(gè)特定的代數(shù)問(wèn)題 Q 將會(huì)成為一個(gè) NP 完全問(wèn)題。幾年后，計(jì)算機(jī)科學(xué)家們?cè)俅伟l(fā)現(xiàn)，如果（屆時(shí)已經(jīng)非常有名的）BAR 猜想成立，那么 Q 將會(huì)擁有多項(xiàng)式級(jí)的算法。把兩者結(jié)合起來(lái)，于是得到：如果 FOO 和 BAR 都成立，那么 P=NP。
接下來(lái)的兩個(gè)世紀(jì)里，這兩個(gè)猜想都有了相當(dāng)充分的研究。人們不斷地得出各式各樣的部分結(jié)果，剩余的特例則被轉(zhuǎn)化為新的形式，直至每個(gè)猜想都被歸為一句非常簡(jiǎn)明、非常具體的命題。最終，兩組人馬相繼宣布，這兩個(gè)命題都是正確的。第一組人馬在 FOO 的誕辰前三周宣布，他們終于攻克了 BAR 猜想的最后一環(huán)。三個(gè)月后，第二組人馬宣布，F(xiàn)OO 猜想正式得以解決。
未來(lái)究竟會(huì)發(fā)生什么？讓我們拭目以待。