著名的 P=NP 問題到底是什么？

大家好，我是貓哥。我最近在追一部熱播的電視劇《天才基本法》，它反復提到了“P=NP”問題。這可是一個天大的難題，在 2000 年克雷數(shù)學研究所公布的千禧年七大數(shù)學難題中，P 和 NP 問題排在了第一位！網(wǎng)上有比較多的科普文章，但較多為泛泛而談。經(jīng)過仔細篩選，我今天給大家分享一篇長文，大家可以收藏慢慢閱讀。（PS：以下內(nèi)容為作者 2006 年及 2022 年兩篇文章合并而成，為便于閱讀，內(nèi)容略有改動。）

來源：http://www.matrix67.com/blog/archives/105

你會經(jīng)常看到網(wǎng)上出現(xiàn)“這怎么做，這不是NP問題嗎”、“這個只有搜了，這已經(jīng)被證明是NP問題了”之類的話。這或許是眾多OIer最大的誤區(qū)之一。你要知道，大多數(shù)人此時所說的NP問題其實都是指的NPC問題。他們沒有搞清楚NP問題和NPC問題的概念。NP問題并不是那種“只有搜才行”的問題，NPC問題才是。

好，行了，基本上這個誤解已經(jīng)被澄清了。下面的內(nèi)容都是在講什么是P問題，什么是NP問題，什么是NPC問題，你如果不是很感興趣就可以不看了。接下來你可以看到，把NP問題當成是 NPC問題是一個多大的錯誤。

還是先用幾句話簡單說明一下時間復雜度。時間復雜度并不是表示一個程序解決問題需要花多少時間，而是當問題規(guī)模擴大后，程序需要的時間長度增長得有多快。

也就是說，對于高速處理數(shù)據(jù)的計算機來說，處理某一個特定數(shù)據(jù)的效率不能衡量一個程序的好壞，而應該看當這個數(shù)據(jù)的規(guī)模變大到數(shù)百倍后，程序運行時間是否還是一樣，或者也跟著慢了數(shù)百倍，或者變慢了數(shù)萬倍。不管數(shù)據(jù)有多大，程序處理花的時間始終是那么多的，我們就說這個程序很好，具有O(1)的時間復雜度，也稱常數(shù)級復雜度；數(shù)據(jù)規(guī)模變得有多大，花的時間也跟著變得有多長，這個程序的時間復雜度就是O(n)，比如找n個數(shù)中的最大值；而像冒泡排序、插入排序等，數(shù)據(jù)擴大2倍，時間變慢4倍的，屬于O(n^2)的復雜度。

還有一些窮舉類的算法，所需時間長度成幾何階數(shù)上漲，這就是O(a^n)的指數(shù)級復雜度，甚至O(n!)的階乘級復雜度。不會存在O(2*n^2)的復雜度，因為前面的那個“2”是系數(shù)，根本不會影響到整個程序的時間增長。同樣地，O (n^3+n^2)的復雜度也就是O(n^3)的復雜度。

因此，我們會說，一個O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，盡管在n很小的時候，前者優(yōu)于后者，但后者時間隨數(shù)據(jù)規(guī)模增長得慢，最終O(n^3)的復雜度將遠遠超過O(n^2)。我們也說，O(n^100)的復雜度小于O(1.01^n)的復雜度。

容易看出，前面的幾類復雜度被分為兩種級別，其中后者的復雜度無論如何都遠遠大于前者：一種是O(1)，O(log(n))，O(n^a)等，我們把它叫做多項式級的復雜度，因為它的規(guī)模n出現(xiàn)在底數(shù)的位置；另一種是O(a^n)和O(n!)型復雜度，它是非多項式級的，其復雜度計算機往往不能承受。

當我們在解決一個問題時，我們選擇的算法通常都需要是多項式級的復雜度，非多項式級的復雜度需要的時間太多，往往會超時，除非是數(shù)據(jù)規(guī)模非常小。

自然地，人們會想到一個問題：會不會所有的問題都可以找到復雜度為多項式級的算法呢？很遺憾，答案是否定的。有些問題甚至根本不可能找到一個正確的算法來，這稱之為“不可解問題”(Undecidable Decision Problem)。The Halting Problem就是一個著名的不可解問題，在我的Blog上有過專門的介紹和證明。再比如，輸出從1到n這n個數(shù)的全排列。不管你用什么方法，你的復雜度都是階乘級，因為你總得用階乘級的時間打印出結果來。

有人說，這樣的“問題”不是一個“正規(guī)”的問題，正規(guī)的問題是讓程序解決一個問題，輸出一個“YES”或“NO”（這被稱為判定性問題），或者一個什么什么的最優(yōu)值（這被稱為最優(yōu)化問題）。那么，根據(jù)這個定義，我也能舉出一個不大可能會有多項式級算法的問題來：Hamilton回路。

問題是這樣的：給你一個圖，問你能否找到一條經(jīng)過每個頂點一次且恰好一次（不遺漏也不重復）最后又走回來的路（滿足這個條件的路徑叫做Hamilton回路）。這個問題現(xiàn)在還沒有找到多項式級的算法。事實上，這個問題就是我們后面要說的NPC問題。

下面引入P類問題的概念：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。P是英文單詞多項式的第一個字母。哪些問題是P類問題呢？通常NOI和NOIP不會出不屬于P類問題的題目。我們常見到的一些信息奧賽的題目都是P問題。道理很簡單，一個用窮舉換來的非多項式級時間的超時程序不會涵蓋任何有價值的算法。

接下來引入NP問題的概念。這個就有點難理解了，或者說容易理解錯誤。在這里強調(diào)（回到我竭力想澄清的誤區(qū)上），NP問題不是非P類問題。NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。

比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準?，F(xiàn)在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小于100個單位長度的路線。它根據(jù)數(shù)據(jù)畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權值加起來一看，嘿，神了，路徑長度98，比100小。于是答案出來了，存在比100小的路徑。別人會問他這題怎么做出來的，他就可以說，因為我找到了一個比100 小的解。

在這個題中，找一個解很困難，但驗證一個解很容易。驗證一個解只需要O(n)的時間復雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那么，只要我RP好，猜得準，我一定能在多項式的時間里解決這個問題。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會來騙我去選它。這就是NP問題。

當然有不是NP問題的問題，即你猜到了解但是沒用，因為你不能在多項式的時間里去驗證它。下面我要舉的例子是一個經(jīng)典的例子，它指出了一個目前還沒有辦法在多項式的時間里驗證一個解的問題。很顯然，前面所說的Hamilton回路是NP問題，因為驗證一條路是否恰好經(jīng)過了每一個頂點非常容易。但我要把問題換成這樣：試問一個圖中是否不存在Hamilton回路。這樣問題就沒法在多項式的時間里進行驗證了，因為除非你試過所有的路，否則你不敢斷定它“沒有Hamilton回路”。

之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快明白，信息學中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關系。

很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關鍵是，人們想知道，是否所有的NP問題都是P類問題。

我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有 NP問題劃進另一個集合NP中，那么，顯然有P屬于NP?，F(xiàn)在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP。

NP問題一直都是信息學的巔峰。巔峰，意即很引人注目但難以解決。在信息學研究中，這是一個耗費了很多時間和精力也沒有解決的終極問題，好比物理學中的大統(tǒng)一和數(shù)學中的歌德巴赫猜想等。

目前為止這個問題還“啃不動”。但是，一個總的趨勢、一個大方向是有的。人們普遍認為，P=NP不成立，也就是說，多數(shù)人相信，存在至少一個不可能有多項式級復雜度的算法的NP問題。

人們?nèi)绱藞孕臥≠NP是有原因的，就是在研究NP問題的過程中找出了一類非常特殊的NP問題叫做NP-完全問題，也即所謂的 NPC問題。C是英文單詞“完全”的第一個字母。正是NPC問題的存在，使人們相信P≠NP。下文將花大量篇幅介紹NPC問題，你從中可以體會到NPC問題使P=NP變得多么不可思議。

為了說明NPC問題，我們先引入一個概念——約化(Reducibility，有的資料上叫“歸約”)。

簡單地說，一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。

《算法導論》上舉了這么一個例子。比如說，現(xiàn)在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應兩個問題，那么我們能找到一個“規(guī)則”，按照這個規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結果。這個規(guī)則即是：兩個方程的對應項系數(shù)不變，一元二次方程的二次項系數(shù)為0。按照這個規(guī)則把前一個問題轉(zhuǎn)換成后一個問題，兩個問題就等價了。

同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點相連即這兩點距離為0，兩點不直接相連則令其距離為1，于是問題轉(zhuǎn)化為在TSP問題中，是否存在一條長為0的路徑。Hamilton回路存在當且僅當TSP問題中存在長為0的回路。

“問題A可約化為問題B”有一個重要的直觀意義：B的時間復雜度高于或者等于A的時間復雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間復雜度比A的時間復雜度還低了，那A的算法就可以改進為B的算法，兩者的時間復雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決后者。

很顯然，約化具有一項重要的性質(zhì)：約化具有傳遞性。如果問題A可約化為問題B，問題B可約化為問題C，則問題A一定可約化為問題C。這個道理非常簡單，就不必闡述了。

現(xiàn)在再來說一下約化的標準概念就不難理解了：如果能找到這樣一個變化法則，對任意一個程序A的輸入，都能按這個法則變換成程序B的輸入，使兩程序的輸出相同，那么我們說，問題A可約化為問題B。

當然，我們所說的“可約化”是指的可“多項式地”約化(Polynomial-time Reducible)，即變換輸入的方法是能在多項式的時間里完成的。約化的過程只有用多項式的時間完成才有意義。

好了，從約化的定義中我們看到，一個問題約化為另一個問題，時間復雜度增加了，問題的應用范圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找復雜度更高，但應用范圍更廣的算法來代替復雜度雖然低，但只能用于很小的一類問題的算法。

再回想前面講的P和NP問題，聯(lián)想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復雜的大NP問題，那么最后是否有可能找到一個時間復雜度最高，并且能“通吃”所有的 NP問題的這樣一個超級NP問題？

答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。

這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC 問題，也就是NP-完全問題。NPC問題的出現(xiàn)使整個NP問題的研究得到了飛躍式的發(fā)展。我們有理由相信，NPC問題是最復雜的問題。

再次回到全文開頭，我們可以看到，人們想表達一個問題不存在多項式的高效算法時應該說它“屬于NPC問題”。此時，我的目的終于達到了，我已經(jīng)把NP問題和NPC問題區(qū)別開了。

到此為止，本文已經(jīng)寫了近5000字了，我佩服你還能看到這里來，同時也佩服一下自己能寫到這里來。

NPC問題的定義非常簡單。同時滿足下面兩個條件的問題就是NPC問題。首先，它得是一個NP問題；然后，所有的NP問題都可以約化到它。證明一個問題是 NPC問題也很簡單。先證明它至少是一個NP問題，再證明其中一個已知的NPC問題能約化到它（由約化的傳遞性，則NPC問題定義的第二條也得以滿足；至于第一個NPC問題是怎么來的，下文將介紹），這樣就可以說它是NPC問題了。

既然所有的NP問題都能約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法，那么所有的NP問題都能用這個算法解決了，NP也就等于P 了。因此，給NPC找一個多項式算法太不可思議了。因此，前文才說，“正是NPC問題的存在，使人們相信P≠NP”。我們可以就此直觀地理解，NPC問題目前沒有多項式的有效算法，只能用指數(shù)級甚至階乘級復雜度的搜索。

順便講一下NP-Hard問題。NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比 NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復雜度更高從而更難以解決。

不要以為NPC問題是一紙空談。NPC問題是存在的。確實有這么一個非常具體的問題屬于NPC問題。下文即將介紹它。

下文即將介紹邏輯電路問題。這是第一個NPC問題。其它的NPC問題都是由這個問題約化而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”。

邏輯電路問題是指的這樣一個問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True。

什么叫做邏輯電路呢？一個邏輯電路由若干個輸入，一個輸出，若干“邏輯門”和密密麻麻的線組成。看下面一例，不需要解釋你馬上就明白了。

這是個較簡單的邏輯電路，當輸入1、輸入2、輸入3分別為True、True、False或False、True、False時，輸出為True。

有輸出無論如何都不可能為True的邏輯電路嗎？有。下面就是一個簡單的例子。 

上面這個邏輯電路中，無論輸入是什么，輸出都是False。我們就說，這個邏輯電路不存在使輸出為True的一組輸入。

回到上文，給定一個邏輯電路，問是否存在一種輸入使輸出為True，這即邏輯電路問題。

邏輯電路問題屬于NPC問題。這是有嚴格證明的。它顯然屬于NP問題，并且可以直接證明所有的NP問題都可以約化到它（不要以為NP問題有無窮多個將給證明造成不可逾越的困難）。證明過程相當復雜，其大概意思是說任意一個NP問題的輸入和輸出都可以轉(zhuǎn)換成邏輯電路的輸入和輸出（想想計算機內(nèi)部也不過是一些 0和1的運算），因此對于一個NP問題來說，問題轉(zhuǎn)化為了求出滿足結果為True的一個輸入（即一個可行解）。

有了第一個NPC問題后，一大堆NPC問題就出現(xiàn)了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題約化到它就行了。后來，Hamilton 回路成了NPC問題，TSP問題也成了NPC問題?，F(xiàn)在被證明是NPC問題的有很多，任何一個找到了多項式算法的話所有的NP問題都可以完美解決了。因此說，正是因為NPC問題的存在，P=NP變得難以置信。

P=NP問題還有許多有趣的東西，有待大家自己進一步的挖掘。攀登這個信息學的巔峰是我們這一代的終極目標?，F(xiàn)在我們需要做的，至少是不要把概念弄混淆了。

Python貓注：以上文章寫于 2006 年，巧合的是在我讀到這篇文章的兩個月前，原作者又更新了一篇《16年后重談P和NP問題》的文章。你已讀到了這里，說明對此話題很感興趣，為了方便大家閱讀，我把新文也一并分享出來：

來源：http://www.matrix67.com/blog/archives/7084#more-7084

2006 年，我在博客（當時還是 MSN Space）上發(fā)了 《什么是 P 問題、NP 問題和 NPC 問題》 一文。這是我高二搞信息學競賽時隨手寫的一些東西，是我的博客中最早的文章之一。今天偶然發(fā)現(xiàn)，這篇現(xiàn)在看了恨不得重寫一遍的“科普”竟仍然有比較大的閱讀量。時間過得很快?！缎请H爭霸》（StarCraft）出了續(xù)作，德國隊 7 比 1 大勝東道主巴西，《學徒》（The Apprentice）里的那個家伙當了總統(tǒng)，非典之后竟然出了更大的疫情。現(xiàn)在已經(jīng)是 2022 年了。這 16 年的時間里，我讀了大學，出了書，娶了老婆，養(yǎng)了娃。如果現(xiàn)在的我寫一篇同樣話題的科普文章，我會寫成什么樣呢？正好，我的新書《神機妙算：一本關于算法的閑書》中有一些相關的內(nèi)容。我從書里的不同章節(jié)中摘選了一些片段，整理加工了一下，弄出了下面這篇文章，或許能回答剛才的問題吧。

有一天，我和老婆去超市大采購。和往常一樣，結完賬之后，我們需要小心謹慎地規(guī)劃把東西放進購物袋的順序，防止東西被壓壞。這并不是一件容易的事情，尤其是考慮到各個物體自身的重量和它能承受的重量之間并無必然聯(lián)系。雞蛋、牛奶非常重，但同時也很怕壓；毛巾、衛(wèi)生紙都很輕，但卻能承受很大的壓力。

于是，我突然想到了這么一個問題：給定 n 個物體各自的重量和它能承受的最大重量，判斷出能否把它們疊成一摞，使得所有的物體都不會被壓壞（一個物體不會被壓壞的意思就是，它上面的物體的總重小于等于自己能承受的最大重量）。

事實證明，這是一個非常有趣的問題——老婆聽完這個問題后整日茶飯不思，晚上做夢都在念叨著自己構造的測試數(shù)據(jù)。這里，我們不妨給出一組數(shù)據(jù)供大家玩玩。

假設有 A、B、C、D 四個物體，其中：物體 A 的自重為 1，最大承重為 9；物體 B 的自重為 5，最大承重為 2；物體 C 的自重為 2，最大承重為 4；物體 D 的自重為 3，最大載重為 12。在這個例子中，安全的疊放方式是唯一的，你能找出來嗎？

答案：C 在最上面，其次是 B，其次是 A，最下面是 D。注意，在這個最優(yōu)方案中，最上面的物體既不是自身重量最小的，也不是承重極限最小的，而是自身重量與承重極限之和最小的。事實上，最優(yōu)方案中的四個物體就是按照這個和的大小排列的！對于某種疊放方案中的某一個物體，不妨把它的最大載重減去實際載重的結果叫作它的安全系數(shù)。

我們可以證明，這種按自身重量與載重能力之和排序的疊放策略可以讓最危險的物體盡可能安全，也就是讓最小的那個安全系數(shù)達到最大。如果此時所有物體的安全系數(shù)都是非負數(shù)，那么我們就相當于有了一種滿足要求的疊放方案；如果此時仍然存在負的安全系數(shù)，那么我們就永遠找不到讓所有物體都安全的疊放方案了。

假設在某種疊放方案中，有兩個相鄰的物體，上面那個物體的自身重量和最大載重分別為 W1 和 P1，下面那個物體的自身重量和最大載重分別為 W2 和 P2。再假設它倆之上的所有物體的重量之和是 W，這是這兩個物體都要承擔的重量。如果 W1 + P1 大于 W2 + P2，那么把這兩個物體的位置交換一下，會發(fā)生什么事情呢？原先下面那個物體的安全系數(shù)為 P2 ? W ? W1，移到上面去之后安全系數(shù)變成了 P2 ? W，這無疑使它更安全了。原先上面那個物體的安全系數(shù)為 P1 ? W，移到下面后安全系數(shù)變成了 P1 ? W ? W2，這個值雖然減小了，但卻仍然大于原先另一個物體的安全系數(shù) P2 ? W ? W1（這里用到了 W1 + P1 > W2 + P2 的假設）。因此，交換兩個物體之后，不但不會刷新安全系數(shù)的下限，相反有時還能向上改進它。

所以說，我們可以不斷地把自身重量與載重能力之和更小的物體換到上面去，反正這不會讓情況變得更糟。最終得到的最優(yōu)方案，也就與我們前面給出的結論一致了。

為了解決某類問題，我們經(jīng)常需要給出一個策略，或者說一個方案，或者說一個處理過程，或者說一系列操作規(guī)則，或者更貼切的，一套計算方法。這就是所謂的“算法” （algorithm）。

讓我們來總結一下。我們的問題是：給定 n 個物體各自的重量，以及每個物體最大可以承受的重量，判斷出能否把它們疊成一摞，使得所有的物體都不會被壓壞。它的算法則是：按照自身重量與最大承重之和進行排序，然后檢驗這是否能讓所有物體都不被壓壞，它的答案就決定了整個問題的答案。有了算法后，實際的計算過程一般就會交給計算機來完成的。程序員的工作，就是編寫代碼，把算法告訴計算機。

讓計算機把每個物體的自身重量和最大承重加起來，這好辦。如果有 n 個物體，那就要算 n 遍加法。給它們排序的時候，我們要依次做下面這些事情：

• 把 n 個數(shù)逐一過一遍，找出最小的那個數(shù)（n 次操作）
• 把最小的那個數(shù)放到第 1 個位置（1 次操作）
• 把剩下的 n ? 1 個數(shù)逐一過一遍，找出最小的那個數(shù)（n ? 1 次操作）
• 把最小的那個數(shù)放到第 2 個位置（1 次操作）
• ……

這要用 n + 1 + (n ? 1) + 1 + … + 1 + 1 = (n2 + 3n) / 2 次操作。物體從上到下該怎么擺，現(xiàn)在就知道了。為了檢驗有沒有東西被壓壞，則需要把物體的重量從上到下累加一遍，邊加邊要和下一個物體的承重做比較?？紤]到最上面的物體不用做檢驗，操作次數(shù)姑且就算 2(n ? 1) 吧。這樣的話，整個算法需要 (n2 + 9n) / 2 ? 2 次操作。當然，在編寫程序時，一些細節(jié)處可能還需要很多額外的操作。不過，對于運算速度極快的計算機來說，這都可以忽略不計。

計算機動輒處理成千上萬的數(shù)據(jù)，多那么一兩次操作不會從根本上影響整個處理過程的開銷。為了評估處理數(shù)據(jù)的效率，我們更應該關注總操作次數(shù)的“級別”。我們甚至可以把 (n2 + 3n) / 2 次操作、(n2 + 9n) / 2 ? 2 次操作以及 2n2 + n + 1 次操作、10n2 ? 13n + 500 次操作等等，統(tǒng)統(tǒng)都叫作“操作次數(shù)以 n2 的級別增長”，它們都代表著同一個意思：當 n 很大的時候，如果 n 變成了原來的 k 倍，那么總的開銷大致就會變成原來的 k2 倍。

1894 年，德國數(shù)學家保羅·巴赫曼（Paul Bachmann）提出了一種使用起來非常方便的“大 O 記號”（big O notation），用到這里真是再適合不過了。如果某個函數(shù) f(n) 的增長速度不超過 n2 的級別，那么我們就可以記下 f(n) = O(n2)。因而，隨著 n 的增加，(n2 + 3n) / 2 、(n2 + 9n) / 2 ? 2 、2n2 + n + 1 、10n2 ? 13n + 500 的增長速度都可以用 O(n2) 來表示。類似地，n3 / 10、(n3 + 3n) / 2、10n3 ? 6n2 + 100 則都相當于 O(n3)。

完成剛才那個算法需要的操作次數(shù)是 O(n2) 級別的。假設每次操作耗時相同，那么運行這個算法所需要的時間也應該是 O(n2) 級別的。更專業(yè)的說法則是，整個算法的“時間復雜度”（time complexity）為 O(n2)。

1985 年由英特爾公司推出的 80386 芯片每秒鐘可以執(zhí)行 200 萬個指令，1999 年的英特爾奔騰 III 處理器每秒鐘可以執(zhí)行 20 億個指令，2012 年的英特爾酷睿 i7 處理器每秒則可以執(zhí)行 1000 億個以上的指令。

不妨假設，當 n = 10 的時候，借助上述算法，計算機只需要 0.1 毫秒就能得到答案。算法的時間復雜度為 O(n2)，說明當 n 增加到原來的 100 倍時，運行完成所需的時間會增加到原來的 10000 倍。因此，如果 n 變成了 1000 時，計算機也只需要 1 秒就能得到答案。即使 n 增加到了 100000，計算機也只需要 10000 秒就能得到答案，這大約相當于 2 個小時又 47 分鐘。

其實，為了判斷出這些物體能否安全疊放，我們似乎完全不必如此煞費心機。我們還有一個更基本的方法：枚舉所有可能的疊放順序，看看有沒有滿足要求的方案。n 個物體一共會產(chǎn)生 n! 種不同的疊放順序，每次檢驗都需要耗費 O(n) 的時間。所以，為了得到答案，最壞情況下的時間復雜度為 O(n · n!)。

那么，我們?yōu)槭裁床徊捎眠@種粗暴豪爽的算法呢？主要原因大概就是，這種算法的時間復雜度有些太高。但是，既然計算機的運算速度如此之快，O(n · n!) 的時間復雜度想必也不在話下吧？讓我們來看一看。仍然假設 n = 10 的時候，計算機只需要 0.1 毫秒就能得到答案。令人吃驚的是，若真的以 O(n · n!) 的級別增長，到了 n = 15 的時候，完成算法全過程需要的時間就已經(jīng)增加到了 54 秒。當 n = 20 時，算法全過程耗時 1.34 億秒，這相當于 1551 天，也就是 4.25 年。當 n = 30 時，算法全過程耗時 700 萬億年，而目前的資料顯示，宇宙大爆炸也不過是在 137 億年以前。如果 n = 100 的話，計算機需要不分晝夜地工作 8.15 × 10140 年才能得到答案。根據(jù)目前的宇宙學理論，到了那個時候，整個宇宙早已一片死寂。

為什么 O(n2) 和 O(n · n!) 的差異那么大呢？原因就是，前者畢竟屬于多項式級的增長，后者則已經(jīng)超過了指數(shù)級的增長。

指數(shù)級的增長真的非?？膳?，雖然 n 較小的時候看上去似乎很平常，但它很快就會超出你的想象，完全處于失控狀態(tài)。一張紙對折一次會變成 2 層，再對折一次會變成 4 層……如此下去，每對折一次這個數(shù)目便會翻一倍。因此，一張紙對折了 n 次后，你就能得到 2n 層紙。當 n = 5 時，紙張層數(shù) 2n = 32；當 n = 10 時，紙張層數(shù)瞬間變成了 1024；當 n = 30 時，你面前將出現(xiàn) 230 = 1 073 741 824 層紙！一張紙的厚度大約是 0.1 毫米，這十億多張紙疊加在一起，也就有 10 萬多米?？ㄩT線（Kármán line）位于海拔 100 千米處，是國際標準規(guī)定的外太空與地球大氣層的界線。這表明，把一張紙對折 30 次以后，其總高度將會超出地球的大氣層，直達外太空。

波斯史詩《王書》記載的故事也形象地道出了指數(shù)級增長的猛烈程度。一位智者發(fā)明了國際象棋，國王想要獎賞他，問他想要什么。智者說：“在這個棋盤的第一個格子里放上一顆大米，第二個格子里放上兩顆大米，第三個格子里放上四顆大米，以此類推，每個格子里的大米數(shù)都是前一個格子的兩倍。所有 64 個格子里的大米就是我想要的獎賞了?！眹跤X得這很容易辦到，便欣然同意了。殊不知，哪怕只看第 64 個格子里的大米，就已經(jīng)有 263 ≈ 9.22 × 1019 顆了。如果把這些大米分給當時世界上的每個人，那么每一個人都會得到上千噸大米。國際象棋的棋盤里幸好只有 64 個格子。如果國際象棋的棋盤里有 300 個格子，里面的大米顆數(shù)就會超過全宇宙的原子總數(shù)了。

因而，在計算機算法領域，我們有一個最基本的假設：所有實用的、快速的、高效的算法，其時間復雜度都應該是多項式級別的。因此，在為計算機編寫程序解決實際問題時，我們往往希望算法的時間復雜度是多項式級別的。

這里的“問題”一詞太過寬泛，可能會帶來很多麻煩，因而我們規(guī)定，接下來所說的問題都是指的“判定性問題”（decision problem），即那些給定某些數(shù)據(jù)之后，要求回答“是”或者“否”的問題。

在復雜度理論中，如果某個判定性問題可以用計算機在多項式級別的時間內(nèi)解出，我們就說這個問題是一個 P 問題，或者說它屬于集合 P。這里，P 是“多項式”的英文單詞 polynomial 的第一個字母。之前那個疊放東西的問題，就是一個 P 問題。

歷史上至少有過兩個問題，它們看起來非常困難，非常不像 P 問題，但在人們的不懈努力之下，最終還是成功地加入了 P 問題的大家庭。其中一個是線性規(guī)劃（linear programming），它是一種起源于二戰(zhàn)時期的運籌學模型。1947 年，喬治·丹齊格（George Dantzig）提出了一種非常漂亮的算法叫作“單純形法”（simplex algorithm），它在隨機數(shù)據(jù)中的表現(xiàn)極為不錯，但在最壞情況下卻需要耗費指數(shù)級的時間。因此，很長一段時間，人們都在懷疑，線性規(guī)劃是否有多項式級的算法。直到 1979 年，人們才迎來了線性規(guī)劃的第一個多項式級的算法，它是由前蘇聯(lián)數(shù)學家列昂尼德·哈奇揚（Leonid Khachiyan）提出的。

另外一個問題則是質(zhì)數(shù)判定問題（primality test）：判斷一個正整數(shù)是否是質(zhì)數(shù)（prime），或者說判斷一個正整數(shù)是不是無法分成兩個更小的正整數(shù)之積。人們曾經(jīng)提出過各種質(zhì)數(shù)判定的多項式級算法，但它們要么是基于概率的，要么是基于某些假設的，要么是有一定適用范圍的。2002 年，來自印度理工學院坎普爾分校的阿格拉瓦爾（M. Agrawal）、卡亞勒（N. Kayal）和薩克斯泰納（N. Saxena）發(fā)表了一篇重要的論文《PRIMES is in P》，給出了第一個確定性的、時間復雜度為多項式級別的質(zhì)數(shù)判定算法，質(zhì)數(shù)判定問題便也歸入了 P 問題的集合。

同時，我們也有很多游離于集合 P 之外的問題。互聯(lián)網(wǎng)安全高度依賴于一種叫作 RSA 算法的加密體系，里面用到了非常犀利的一點：在整數(shù)世界里，合成與分解的難度是不對等的。任意選兩個比較大的質(zhì)數(shù)，比如 19 394 489 和 27 687 937。我們能夠很容易計算出它倆相乘的結果，它等于 536 993 389 579 193；但是，如果反過來問你，536 993 389 579 193 可以分解成哪兩個質(zhì)數(shù)的乘積，這卻非常難以迅速作答。把一個大整數(shù)分解成若干個質(zhì)數(shù)之積，這就是著名的“整數(shù)分解問題”（integer factorization problem）。目前，人們還沒有找到一種快速有效的整數(shù)分解算法。也就是說，目前人們還不知道整數(shù)分解問題是否屬于 P。（這里我們指的也是整數(shù)分解問題的判定性版本，即給定一個正整數(shù) N 和一個小于 N 的正整數(shù) M，判斷出 N 是否能被某個不超過 M 的數(shù)整除。）人們猜測，整數(shù)分解很可能不屬于 P。這正是 RSA 算法目前足夠安全的原因。

另一個著名的問題叫作“子集和問題”（subset sum problem）：給定一個整數(shù)集合 S 以及一個大整數(shù) M，判斷出能否在 S 里選出一些數(shù)，使得它們的和正好為 M？比方說，假設集合 S 為

{38, 71, 45, 86, 68, 65, 82, 89, 84, 85, 91, 8}

并且大整數(shù) M = 277，那么你就需要判斷出，能否在上面這一行數(shù)里選出若干個數(shù)，使得它們相加之后正好等于 277。為了解決這類問題，其中一種算法就是，枚舉所有可能的選數(shù)方案，看看有沒有滿足要求的方案。如果我們用 n 來表示集合里的元素個數(shù)，那么所有可能的選數(shù)方案就有 O(2n) 種，檢驗每一種方案都需要花費 O(n) 的時間，因而整個算法的時間復雜度為 O(n · 2n)。雖然人們已經(jīng)找到了時間復雜度更低的算法，但沒有一種算法的時間復雜度是多項式級別的。人們猜測，子集和問題很可能也不屬于 P。

美國計算機科學家杰克·埃德蒙茲（Jack Edmonds）在 1964 年的一篇討論某個矩陣問題的論文中，也提到了類似于 P 問題的概念：“當然，給定一個矩陣后，考慮所有可能的染色方案，我們一定能碰上一個符合要求的剖分，但這種方法所需要的工作量大得驚人。我們要尋找一種算法，使得隨著矩陣大小的增加，工作量僅僅是呈代數(shù)式地上漲……和大多數(shù)組合問題一樣，找出一個有限的算法很容易，找出一個滿足上述條件的，從而能在實際中運用的算法，就不那么容易了?！?/p>

接下來，埃德蒙茲模模糊糊地觸碰到了一個新的概念：“給定一個矩陣，它的各列最少能被剖分成多少個獨立集？我們試著找出一個好的刻畫方式。至于什么叫作‘好的刻畫’，我們則采用‘絕對主管原則’。一個好的刻畫，應該能透露出矩陣的某些信息，使得某個主管能夠在助手找到一個最小的剖分方案之后，輕易地驗證出這確實是最小的剖分方案。有了一個好的刻畫，并不意味著就有一個好的算法。助手很可能還是得拼死拼活，才能找到那個剖分方案?！?/p>

埃德蒙茲后面所說的，不是設計一種多項式級的算法來尋找答案，而是設計一種多項式級的算法來驗證答案的正確性。對于很多問題，這件事情是很好辦的。為了向人們展示出確實有可能讓所有的物體都不被壓壞，我們只需要給出一種滿足要求的物體疊放順序，并讓計算機用 O(n) 的時間驗證它的確滿足要求即可。為了向人們展示出集合中的某些數(shù)加起來能得出 277，我們只需要提供一種選數(shù)的方法，并讓計算機用 O(n) 的時間求和檢驗。

對于有些問題來說，如果答案是肯定的，我們可能并沒有一種非常明顯的高效方法來檢驗這一點。不過，很容易看出，找出一個多項式級的答案驗核算法，再怎么也比找出一個多項式級的答案獲取算法更容易。很多看上去非常困難的問題，都是先找到多項式級的答案驗核算法，再找到多項式級的答案獲取算法的。

一個經(jīng)典的例子就是質(zhì)數(shù)判定問題。如果某個數(shù)確實是一個質(zhì)數(shù)，你怎樣才能在多項式級的時間里證明這一點？1975 年，沃恩·普拉特（Vaughan Pratt）在《每個質(zhì)數(shù)都有一份簡短的證明書》（Every Prime Has a Succinct Certificate）一文中給出了一種這樣的方法，無疑推動了質(zhì)數(shù)判定算法的發(fā)展。

還有些問題是如此之難，以至于目前人們不但沒有找到多項式級的答案獲取算法，而且還不知道是否存在多項式級的答案驗核算法。比如經(jīng)典的“第 K 大子集問題”（Kth largest subset problem）：給定一個含有 n 個整數(shù)的集合 S，一個大整數(shù) M，以及一個不超過 2n 的整數(shù) K，判斷出是否存在至少 K 個不同的子集，使得每個子集里的元素之和都不超過 M？如果答案是肯定的，一個很容易想到的驗證方法便是，把所有滿足要求的 K 個子集都列出來，并交由計算機審核。只可惜，子集的數(shù)目是指數(shù)級的，因而審核工作也將會花費指數(shù)級的時間。人們猜測，第 K 大子集問題很可能沒有多項式級別的檢驗方法。

在復雜度理論中，一個問題有沒有高效的答案驗核算法，也是一個非常重要的研究課題。對于一個判定性問題，如果存在一個多項式級的算法，使得每次遇到答案應為“是”的時候，我們都能向這個算法輸入一段適當?shù)摹白C據(jù)”，讓算法運行完畢后就能確信答案確實為“是”，我們就說這個問題是一個 NP 問題，或者說它屬于集合 NP。為了解釋“NP 問題”這個名字的來由，我們不得不提到 NP 問題的另一個等價定義：可以在具備隨機功能的機器上用多項式級的時間解決的問題。

如果允許計算機的指令發(fā)生沖突，比如指令集里面既有 “如果遇到情況 A，則執(zhí)行操作 B”，又有 “如果遇到情況 A，則執(zhí)行操作 C”，我們就認為這樣的計算機具備了隨機的功能。這種新型的計算機就叫作“非確定型”（nondeterministic）機器。機器一旦遇到了矛盾糾結之處，就隨機選擇一條指令執(zhí)行。你可以把機器面對的每一次隨機選擇都想象成是一個通向各個平行世界的岔路口，因而整臺機器可以同時試遍所有的分支，自動探尋所有的可能。如果你看過尼古拉斯·凱奇（Nicolas Cage）主演的電影《預見未來》（Next），你或許會對這一幕非常熟悉。只要在任意一個分支里機器回答了“是”，那么整臺機器也就算作回答了“是”。

在如此強大的機器上，很多問題都不是問題了。為了判斷出能否讓所有的物體都不被壓壞，我們只需要讓機器每次都從剩余物體中隨便選一個放，看看由此產(chǎn)生的 n! 種放法里是否有哪種放法符合要求。為了判斷出集合中是否有某些數(shù)加起來等于 277，我們只需要讓機器隨機決定每個數(shù)該選還是不選，最后看看有沒有哪次選出來的數(shù)之和正好是 277。

事實上，在非確定型計算機上可以用多項式級的時間獲取到答案的問題，正是那些在確定型計算機上可以用多項式級的時間驗核答案的問題，原因很簡單：如果一個問題可以在非確定型計算機上獲解，找到解的那個分支沿途做出的選擇就成了展示答案正確性的最有力證據(jù)；反之，如果我們能在確定型計算機上驗核出答案確實為“是”，我們便可以在非確定型計算機上隨機產(chǎn)生驗核所需的證據(jù)，看看在所有可能的證據(jù)當中會不會出現(xiàn)一條真的能通過驗核的證據(jù)?！胺谴_定型”的英文單詞是 nondeterministic，它的第一個字母是 N；“多項式”的英文單詞是 polynomial，它的第一個字母是 P。NP 問題便如此得名。

容易想到，所有的 P 問題一定都是 NP 問題，但反過來就不好說了。例如，子集和問題是屬于 NP 的。然而，之前我們就曾經(jīng)討論過，人們不但沒有找到子集和問題的多項式級解法，而且也相信子集和問題恐怕根本就沒有多項式級的解法。因而，子集和問題很可能屬于這么一種類型的問題：它屬于集合 NP，卻不屬于集合 P。

1971 年，史提芬·古克（Stephen Cook）發(fā)表了計算機科學領域最重要的論文之一——《定理證明過程的復雜性》（The Complexity of Theorem-Proving Procedures）。在這篇論文里，史提芬·古克提出了一個著名的問題：P 等于 NP 嗎？

如果非要用一句最簡單、最直觀的話來描述這個問題，那就是：能高效地檢驗解的正確性，是否就意味著能高效地找出一個解？數(shù)十年來，無數(shù)的學者向這個問題發(fā)起了無數(shù)次進攻。根據(jù)格哈德·韋金格（Gerhard Woeginger）的統(tǒng)計，僅從 1996 年算起，就有 100 余人聲稱解決了這個問題，其中 55 人聲稱 P 是等于 NP 的，另外 45 人聲稱 P 是不等于 NP 的，還有若干人聲稱這個問題理論上不可能被解決。

但不出所料的是，所有這些“證明”都是錯誤的。目前為止，既沒有人真正地證明了 P = NP，也沒有人真正地證明了 P ≠ NP，也沒有人真正地證明了這個問題的不可解性。這個問題毫無疑問地成為了計算機科學領域最大的未解之謎。

在 2000 年美國克雷數(shù)學研究所（Clay Mathematics Institute）公布的千禧年七大數(shù)學難題（Millennium Prize Problems）中，P 和 NP 問題排在了第一位。第一個解決該問題的人將會獲得一百萬美元的獎金。

讓我們來看一下，科學家們都是怎么看 P 和 NP 問題的吧。英國數(shù)學家、生命游戲（Game of Life）的發(fā)明者約翰·康威（John Conway）認為，P 是不等于 NP 的，并且到了 21 世紀 30 年代就會有人證明這一點。他說道：“我覺得這本來不應該是什么難題，只是這個理論來得太遲，我們還沒有弄出任何解決問題的工具。”

美國計算機科學家、1985 年圖靈獎獲得者理查德·卡普（Richard Karp）也認為，P 是不等于 NP 的。他說：“我認為傳統(tǒng)的證明方法是遠遠不夠的，解決這個問題需要一種絕對新奇的手段。直覺告訴我，這個問題最終會由一位不被傳統(tǒng)思想束縛的年輕科學家解決掉?！?/p>

美國計算機科學家、《自動機理論、語言和計算導論》（Introduction to Automata Theory, Languages and Computation）的作者杰夫瑞·厄爾曼（Jeffrey Ullman）同樣相信 P 不等于 NP。他說：“我認為這個問題和那些困擾人類上百年的數(shù)學難題有得一拼，比如四色定理（four color theorem）。所以我猜測，解決這個問題至少還要 100 年。我敢肯定，解決問題所需的工具至今仍未出現(xiàn)，甚至連這種工具的名字都還沒有出現(xiàn)。但別忘了，那些最偉大的數(shù)學難題剛被提出來的 30 年里，所面對的也是這樣的情況。”

你或許會注意到，大家似乎都傾向于認為 P ≠ NP 。事實上，根據(jù)威廉·加薩奇（William Gasarch）的調(diào)查，超過八成的學者都認為 P ≠ NP。這至少有兩個主要的原因。首先，證明 P = NP 看上去比證明 P ≠ NP 更容易，但即使這樣，目前仍然沒有任何跡象表明 P = NP。為了證明 P = NP，我們只需要構造一種可以適用于一切 NP 問題的超級萬能的多項式級求解算法。在那篇劃時代的論文里，史提芬·古克證明了一個頗有些出人意料的結論，讓 P = NP 的構造性證明看起來更加唾手可得。給你一堆正整數(shù)，問能否把它們分成總和相等的兩堆，這個問題叫作“分區(qū)問題”（partition problem）。

容易看出，分區(qū)問題可以轉(zhuǎn)化為子集和問題的一個特例，你只需要把子集和問題中的目標設定成所有數(shù)之和的一半即可。這說明，子集和問題是一個比分區(qū)問題更一般的“大問題”，它可以用來解決包括分區(qū)問題在內(nèi)的很多“小問題”。史提芬·古克則證明了，在 NP 問題的集合里，存在至少一個最“大”的問題，它的表達能力如此之強，以至于一切 NP 問題都可以在多項式的時間里變成這個問題的一種特例。很容易想到，如果這樣的“終極 NP 問題”有了多項式級的求解算法，所有的 NP 問題都將擁有多項式級的求解算法。這樣的問題就叫作“NP 完全問題”（NP-complete problem）。在論文中，史提芬·古克構造出了一個具體的 NP 完全問題，它涉及到了很多計算機底層的邏輯運算，能蘊含所有的 NP 問題其實也不是非常奇怪的事。

后來，人們還找到了很多其他的 NP 完全問題。1972 年，理查德·卡普發(fā)表了《組合問題中的可歸約性》（Reducibility among Combinatorial Problems）一文。這是復雜度理論當中又一篇里程碑式的論文，“P 問題”、“NP 問題”、“NP 完全問題”等術語就在這里誕生。

在這篇論文里，理查德·卡普列出了 21 個 NP 完全問題，其中不乏一些看起來很“正常”、很“自然”的問題，剛才提到的子集和問題就是其中之一。1979 年，邁克爾·加里（Michael Garey）和戴維·約翰遜（David Johnson）合作出版了第一本與 NP 完全問題理論相關的教材——《計算機和難解性：NP 完全性理論導引》（Computers and Intractability: A Guide to the Theory of NP-Completeness）。該書的附錄中列出了超過 300 個 NP 完全問題，這一共用去了 100 頁的篇幅，幾乎占了整本書的三分之一。

如果這些 NP 完全問題當中的任何一個問題擁有了多項式級的求解算法，所有的 NP 問題都將自動地獲得多項式級的求解算法，P 也就等于 NP 了。然而，這么多年過去了，沒有任何人找到任何一個 NP 完全問題的任何一種多項式解法。這讓人們不得不轉(zhuǎn)而相信，P 是不等于 NP 的。

人們相信 P ≠ NP 的另一個原因是，這個假設經(jīng)受住了實踐的考驗。工業(yè)與生活中的諸多方面都依賴于 P ≠ NP 的假設。如果哪一天科學家們證明了 P = NP，尋找一個解和驗證一個解變得同樣容易，這個世界將會大不一樣。1995 年，魯塞爾·因帕利亞佐（Russell Impagliazzo）對此做了一番生動描述。

首先，各種各樣的 NP 問題，尤其是那些最為困難的 NP 完全問題，都將全部獲得多項式級的解法。工業(yè)上、管理上的幾乎所有最優(yōu)化問題都立即有了高效的求解方案。事實上，我們甚至不需要編程告訴計算機應該怎樣求解問題，我們只需要編程告訴計算機我們想要什么樣的解，編譯器將會自動為我們做好一個高效的求解系統(tǒng)。

其次，很多人工智能問題也迎刃而解了。比方說，為了讓計算機具備中文處理能力，我們可以準備一個訓練集，里面包含一大批句子樣本，每個句子都帶有“符合語法”、“不符合語法”這兩種標記之一。接下來，我們要求計算機構造一個代碼長度最短的程序，使得將這些語句輸入這個程序后，程序能正確得出它們是否符合語法。顯然，這個最優(yōu)化問題本身是一個 NP 問題（這里有個前提，即這樣的程序是存在的，并且是多項式級別的），因此計算機可以在多項式時間內(nèi)找到這個最簡程序。

根據(jù)奧卡姆剃刀原理（Occam’s razor），我們有理由相信，這個程序背后的算法也就是人類頭腦中正在使用的算法，因此它能夠適用于所給材料之外的其他語句，并具有自我學習的功能。數(shù)學家的很多工作也可以完全交給計算機來處理。尋找一個反例和驗證一個反例變得同樣簡單，各種錯誤的猜想都將很快被推翻。事實上，尋找一個數(shù)學證明和驗證一個證明的正確性也變得同樣簡單，因此各種正確的命題也能夠很快找到一個最簡的證明。

最后，不要高興得太早——P = NP 的世界也將會是一個極不安全的世界。電子簽名技術不再有效，因為偽造一段合法的簽名變得和驗證簽名是否合法一樣輕松。RSA 算法也不再有效，因為尋找一個質(zhì)因數(shù)變得和判斷整除性一樣簡單。事實上，發(fā)明任何新的密碼算法都是徒勞——計算機可以根據(jù)一大批明文密文樣本推算出生成密文的算法（只要這個算法本身是多項式的）。

更進一步，在網(wǎng)絡上，你再也沒法把人和人區(qū)別開來，甚至沒法把人和計算機區(qū)別開來。計算機不僅能輕易通過圖靈測試（Turing test），還能精確地模仿某一個特定的人。如果你能把某個人的網(wǎng)絡聊天記錄全部搜集起來，把這個人和網(wǎng)友們的對話全部遞交給計算機，計算機將會很快學會如何模仿這個人。網(wǎng)絡的身份鑒定必須要借助物理手段。即使是在科幻故事中，這樣的設定也相當瘋狂，可見 P = NP 有多不可能了。

雖然種種證據(jù)表明 P ≠ NP，但我們?nèi)匀粺o法排除 P = NP 的可能性。其實，如果 P 真的等于 NP，但時間復雜度的次數(shù)非常大非常大非常大，密碼學的根基仍然不太可能動搖，我們的世界仍然不太可能大變。被譽為“算法分析之父”的計算機科學大師高德納（Donald Knuth）還提出了這樣一種可能：未來有人利用反證法證明了 P = NP，于是我們知道了所有 NP 問題都有多項式級的算法，但算法的時間復雜度究竟是多少，我們?nèi)匀灰粺o所知！

對于很多人來說，找不到任何一個 NP 完全問題的多項式級算法，同樣不應成為質(zhì)疑 P = NP 的理由。荻原光德（Mitsunori Ogihara）認為，最終人們或許會成功地證明 P = NP，但這絕不是一兩個人死死糾纏某一個 NP 完全問題就能辦到的。對此，他做了更為細致的想象。

XX 世紀后期，一份非常簡略的、從未發(fā)表過的草稿，無意中開辟了解決 P 和 NP 問題的道路。這份草稿出自 20 世紀的一位數(shù)學天才 FOO 之手，當時他正在嘗試著建立某種代數(shù)結構的新理論。顯然，F(xiàn)OO 很快放棄了這個想法，并且今后從未重新拾起這個課題。這份草稿一直卡在 FOO 的臥室地板的縫隙里，在后來的一次舊房翻新工程中才被工人們發(fā)現(xiàn)。由于草稿太過簡略，因而當時并未引起太多關注。然而，幾十年后，一群數(shù)學家發(fā)現(xiàn)，如果草稿上面的某個假設的某個變形成立，將會推出很多有意思的東西。雖然這不是 FOO 本來要做的假設，但它還是被人們稱作“FOO 假設”，以紀念這位數(shù)學天才。

大約 100 年后，一群計算機科學家發(fā)現(xiàn)，如果 FOO 假設成立，那么某個特定的代數(shù)問題 Q 將會成為一個 NP 完全問題。幾年后，計算機科學家們再次發(fā)現(xiàn)，如果（屆時已經(jīng)非常有名的）BAR 猜想成立，那么 Q 將會擁有多項式級的算法。把兩者結合起來，于是得到：如果 FOO 和 BAR 都成立，那么 P = NP。

接下來的兩個世紀里，這兩個猜想都有了相當充分的研究。人們不斷地得出各式各樣的部分結果，剩余的特例則被轉(zhuǎn)化為新的形式，直至每個猜想都被歸為一句非常簡明、非常具體的命題。最終，兩組人馬相繼宣布，這兩個命題都是正確的。第一組人馬在 FOO 的誕辰前三周宣布，他們終于攻克了 BAR 猜想的最后一環(huán)。三個月后，第二組人馬宣布，F(xiàn)OO 猜想正式得以解決。

未來究竟會發(fā)生什么？讓我們拭目以待。