1956年3月，在新澤西州普林斯頓的一個雪天，一位身材矮小、外貌像貓頭鷹的男子庫爾特·哥德爾給一位即將去世的朋友寫了最後一封信。哥德爾對約翰·馮·諾伊曼使用了正式的稱呼，儘管兩人作為普林斯頓高等研究院的同事已經認識了幾十年。這兩位都是數學天才，在二戰後的幾年裡，為美國科學和軍事霸權的建立發揮了重要作用。然而，現在馮·諾伊曼患了癌症，即使像哥德爾這樣的天才也無能為力，只能表達一些過於樂觀的客套話，然後轉移話題
尊敬的馮·諾伊曼先生
我懷著極大的悲痛得知您生病了…… 據我所知，最近幾個月您接受了激進的治療，我很高興這種治療如願以償地成功了，您現在的身體狀況也更好了…….
關於支援科學新聞業
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞業 訂閱。透過購買訂閱，您將幫助確保有關塑造我們當今世界的發現和想法的具有影響力的故事能夠繼續流傳下去。
既然您現在感覺更強壯了，我想斗膽給您寫一個數學問題，我很想聽聽您的意見…….
對於非數學家來說，哥德爾對這個問題的描述完全無法理解。（事實上，他可能只是想透過進行一種高度專業的閒聊來轉移馮·諾伊曼對其疾病的注意力。）他想知道假設的機器需要多長時間才能吐出問題的答案。他的結論聽起來像是科幻小說裡的東西
如果真的有[這樣]一臺機器……這將具有最重要的意義。也就是說，這顯然意味著……數學家關於“是”或“否”問題的腦力勞動可以完全被機器取代.
哥德爾所說的“腦力勞動”並不是指像2加2這樣的簡單計算。他指的是數學家為了闡明全新的知識領域而進行的直覺飛躍。25年前，哥德爾現在著名的不完備性定理永遠地改變了數學。能否製造出一臺機器，按需產生類似改變世界的洞見？
在哥德爾寄出信的幾周後，馮·諾伊曼住進了華盛頓特區沃爾特·裡德陸軍醫療中心，不到一年後去世，終生未能回答他朋友的問題。但這個問題比他們兩人都活得更久。哥德爾的問題現在被稱為P與NP問題，後來成為現代計算機科學的組織原則。它催生了一個全新的研究領域，稱為計算複雜性理論——數學、科學和工程學的融合，旨在完全確定地證明計算機在實際條件下能夠做什麼和不能做什麼。
但P與NP問題遠不止我們稱之為計算機的塑膠和矽器件。這個問題對物理學和分子生物學、密碼學、國家安全、進化、數學的極限，甚至可能是現實的本質都具有實際意義。這個問題為我們在理論上永遠能夠計算什麼設定了界限。而在21世紀，計算的極限越來越像人類知識本身的極限。
賭注
邁克爾·西普瑟當時只是一個研究生，但他知道會有人很快解決P與NP問題。他甚至認為自己可能是解決問題的人。那是1975年秋天，他正在與加州大學伯克利分校計算機科學系的同班研究生倫納德·阿德曼討論這個問題。“我對P與NP問題很著迷，感覺自己能夠以一種超越其他人似乎正在接近它的方式來理解它，”西普瑟說，他現在是麻省理工學院數學系主任。他對自己如此有把握，以至於那天與阿德曼打了個賭：P與NP問題將在20世紀末之前解決，甚至更早。賭注的條款是：一盎司純金。
西普瑟的賭注具有某種詩意的意義，因為P與NP問題本身就是一個關於其他問題可以多快解決的問題。有時，簡單地按照步驟清單就能相對快速地達到最終結果。想想去雜貨店購物：你逐項勾選清單上的物品，直到到達清單的末尾。複雜性理論家將這些問題標記為P，代表“多項式時間”，這是一種數學上精確的說法，即無論購物清單變得多麼長，勾選所有物品所需的時間永遠不會以無法控制的速度增長。
相比之下，更多的問題可能實用也可能不實用，無法透過簡單地勾選清單上的物品來解決，但檢查解決方案很容易。拼圖遊戲就是一個很好的例子：即使拼圖可能需要努力才能完成，你也可以透過檢視拼圖來識別正確的解決方案。複雜性理論家將這些快速可檢查的、“類似拼圖遊戲”的問題稱為NP。
在西普瑟下注的四年前，一位名叫斯蒂芬·庫克的數學家證明了這兩種問題是相關的：每個快速可解的P問題也是一個快速可檢查的NP問題。從庫克的洞見中產生的P與NP問題——並且一直困擾著這個領域——詢問反過來是否也成立：所有快速可檢查的問題也都是快速可解的嗎？直觀地說，答案似乎是否定的。識別已完成的拼圖遊戲（“嘿，你拼好了！”）與完成所有工作來找到解決方案是截然不同的。換句話說，P似乎不等於NP。
西普瑟著迷的是，沒有人能夠用數學證明這個看似顯而易見的觀察結果。在沒有證明的情況下，仍然存在一種可能性，無論多麼不可能或奇怪，所有NP問題實際上都可能是偽裝的P問題。P和NP可能相等——並且由於計算機可以輕鬆處理任何P問題，P等於NP將意味著計算機解決問題的能力遠遠超出我們的想象。它們將完全符合哥德爾在給馮·諾伊曼的信中描述的那樣：機械神諭，可以有效地回答幾乎任何向它們提出的問題，只要它們可以被程式設計來驗證解決方案。
西普瑟知道這種結果發生的可能性微乎其微。然而，證明相反的、更可能發生的情況——P不等於NP——同樣具有開創性。
就像哥德爾的不完備性定理揭示了數學必須包含真實但無法證明的命題一樣，證明P不等於NP將揭示一個關於知識侷限性的客觀真理。拼圖遊戲和識別出拼圖已完成是兩件根本不同的事情，無論我們的計算機變得多麼強大，獲得知識都沒有捷徑。
證明否定總是很困難，但哥德爾做到了。因此，對於西普瑟來說，與阿德曼打賭時，25年似乎有足夠的時間來完成這項工作。如果他自己無法證明P不等於NP，其他人也會證明。而他仍然會多得一盎司黃金。
快速變得複雜
阿德曼與西普瑟一樣對這個問題著迷，即使不像西普瑟那樣有信心，因為有一個神秘的數學線索。庫克的論文證明了P問題都是NP問題，同時也證明了一種特殊型別的快速可檢查問題——NP完全問題的存在。這些問題就像一套神奇的鑰匙：如果你找到一種快速演算法來解決其中一個問題，那麼該演算法也將解鎖所有其他NP問題的解決方案，並證明P等於NP。
只有一個問題：NP完全問題是計算機科學領域任何人見過的最難的問題之一。一旦被發現，它們就開始無處不在。在庫克的論文發表後不久，阿德曼在伯克利的導師之一理查德·M·卡普發表了一項里程碑式的研究，表明21個經典的計算問題都是NP完全問題。幾十個，然後是數百個，很快就隨之而來。“這就像從堤壩上拔出一根手指，”阿德曼說。安排航空旅行、將搬家箱子裝進卡車、解決數獨謎題、設計計算機晶片、安排婚禮招待會的客人座位、玩俄羅斯方塊以及數千個其他實際的、現實世界的問題都被證明是NP完全問題。
這個解決P與NP問題的誘人鑰匙怎麼會同時顯得如此普遍又如此難以破解呢？“這就是為什麼我對研究P與NP問題感興趣，”阿德曼說，他現在是南加州大學的教授。“這些計算問題的力量和廣度似乎非常令人敬畏。但我們當然不理解它們。而且似乎我們也不會很快理解它們。”（阿德曼對P與NP問題的悲觀態度導致了一項改變世界的發明：在下注幾年後，阿德曼和他的同事羅納德·李維斯特和阿迪·薩莫爾利用P和NP看似不可通約的性質，建立了他們同名的RSA加密演算法，該演算法仍然廣泛用於網上銀行、通訊和國家安全應用。）
NP完全問題之所以困難，是因為它們快速變得複雜。想象一下，你是一個揹包客，計劃穿越歐洲的多個城市旅行，你想要一條路線，讓你能夠穿過每個城市，同時最大限度地減少你需要旅行的總距離。你如何找到最佳路線？最簡單的方法是嘗試每一種可能性。如果有五個城市要遊覽，你只需要檢查12條可能的路線。如果有10個城市，可能的路線數量就會激增到超過18萬條。如果有60個城市，路徑的數量將超過已知宇宙中原子的數量。這種計算噩夢被稱為旅行商問題，在80多年的深入研究中，沒有人找到一種通用的解決方法，可以比逐一嘗試每一種可能性更好。
這就是NP完全問題——以及P與NP問題的悖論本質：不僅所有NP完全問題都同樣不可能解決，除非在最簡單的情況下——即使你的計算機擁有比上帝更多的記憶體和整個宇宙的生命週期來工作——它們似乎也無處不在。事實上，這些NP完全問題不僅僅讓計算機科學家感到沮喪。它們似乎限制了自然本身的能力。
自然的密碼
先鋒荷蘭程式設計師艾茲格·迪科斯徹明白，計算問題具有超越數學的意義。他曾經說過，“計算機科學與計算機的關係，就像天文學與望遠鏡的關係一樣。”換句話說，計算是一種行為，除了谷歌和英特爾製造的系統外，許多系統都表現出這種行為。事實上，任何透過一組離散規則將輸入轉換為輸出的系統——包括生物學家和物理學家研究的系統——都可以說是正在進行計算。
1994年，數學家彼得·秀爾證明，巧妙排列的亞原子粒子可以破解現代加密方案。2002年，阿德曼使用DNA鏈找到了旅行商問題例項的最佳解決方案。2005年，量子計算專家斯科特·阿倫森（Scott Aaronson）使用肥皂泡有效地計算出了一個被稱為斯坦納樹的問題的最佳解決方案。這些都是典型的NP問題，計算機應該會因此燒燬電路板。這些自然系統是否知道一些計算機不知道的關於P與NP問題的東西？
“當然不是，”阿倫森說。他的肥皂泡實驗實際上是對簡單物理系統可以某種程度上超越P和NP問題之間差異的說法的反證法。雖然肥皂泡確實在少數情況下“計算”出了最小斯坦納樹的完美解決方案，但隨著問題規模的增加，它們很快就失敗了，就像計算機一樣。阿德曼的DNA鏈實驗也碰到了同樣的牆。秀爾的量子演算法在所有情況下都有效，但它破解的因式分解問題幾乎肯定不是NP完全問題。因此，該演算法沒有提供解鎖所有其他NP問題的鑰匙。生物學、經典物理學和量子系統似乎都支援NP完全問題沒有捷徑的觀點。而這隻有在P不等於NP的情況下才是正確的。
“當然，我們仍然無法用確鑿的證據來證明這一點，”阿倫森說。“但是，如果我們是物理學家而不是複雜性理論家，‘P不等於NP’早就被宣佈為自然法則了——就像沒有什麼東西可以比光速更快一樣。”事實上，一些關於宇宙基本性質的物理理論——例如斯蒂芬·霍金關於黑洞的研究提出的全息原理——暗示現實的結構本身不是連續的，而是由離散的位元組成的，就像計算機一樣[參見邁克爾·莫耶的文章“空間是數字化的嗎？”；《大眾科學》，二月]。因此，NP問題的明顯難解性——以及由此暗示的知識侷限性——可能從最基本的層面上就根植於宇宙之中。
大腦機器
因此，如果宇宙本身都受到P與NP問題施加的計算限制的約束，那麼NP完全問題怎麼會似乎總是得到解決呢——即使在某些情況下，找到這些解決方案應該花費數萬億年以上的時間？
例如，當人類胎兒在子宮中發育時，它的大腦會由數十億個獨立的神經元自行連線起來。找到這些細胞的最佳排列方式是一個NP完全問題——進化似乎已經解決了這個問題。“當一個神經元從一個點延伸出來到達一大堆其他突觸點時，這基本上是一個圖最佳化問題，這是一個NP難題，”進化神經生物學家馬克·張吉說。然而，大腦實際上並沒有解決這個問題——它只是做了一個近似的解。（在實踐中，神經元始終在最佳排列方式的3%以內。）即使是隻有302個神經元的秀麗隱杆線蟲，也沒有完美的神經線路圖，儘管數十億代的自然選擇作用於這個問題。“進化受到P與NP問題的約束，”張吉說，“但它仍然有效，因為生命並不總是需要完美才能良好地發揮作用。”
事實證明，計算機也是如此。現代計算機能夠做任何有用的事情——更不用說在我們所有人都認為理所當然的影片遊戲機和智慧手機上實現奇蹟般的壯舉——這證明了P問題包含了我們的大量計算需求。對於其餘的問題，通常一個不完美的近似演算法就足夠了。事實上，這些“足夠好”的演算法可以解決極其複雜的搜尋和模式匹配問題，其中許多問題在技術上是NP完全問題。這些解決方案並不總是數學上在每種情況下都是最優的，但這並不意味著它們沒有用。
以谷歌為例。許多複雜性研究人員認為NP問題本質上是搜尋問題。但據谷歌的研究主管彼得·諾維格稱，該公司煞費苦心地避免處理NP問題。“我們的使用者更關心速度而不是完美，”他說。相反，谷歌的研究人員針對比P（稱為線性時間）更快的計算複雜性類別最佳化他們的演算法，以便搜尋結果幾乎立即出現。如果出現無法以這種方式解決的問題呢？“我們要麼重新構建問題使其更容易解決，要麼就不理會它，”諾維格說。
這就是P與NP問題的遺產和諷刺之處。1956年，哥德爾在給馮·諾伊曼的信中認為，這個問題預示著一個充滿絕對可靠的推理機器的未來，這些機器能夠取代“數學家的腦力勞動”，並透過按下按鈕就能產生大膽的新真理。相反，數十年來對P與NP問題的研究幫助構建了一個世界，在這個世界中，我們透過接受機器的侷限性來擴充套件機器解決問題的能力。逼真的近似，而不是機械的完美，是谷歌的自動駕駛汽車如何在擁擠的拉斯維加斯高速公路上自動駕駛，以及IBM的沃森如何在《危險邊緣》節目中猜謎獲勝的原因。
淘金熱
2000年過去了，西普瑟給阿德曼寄去了一盎司黃金。“我想他希望把它鑲嵌在一個有機玻璃立方體中，這樣他就可以把它放在他的辦公桌上或其他地方，”西普瑟說。“我沒有那樣做。”同年，馬薩諸塞州劍橋市的克雷數學研究所為解決P與NP問題提供了新的賞金：100萬美元。這筆獎金有助於提高這個問題的影響力，但也吸引了業餘愛好者和怪人的注意；如今，像許多著名的複雜性理論家一樣，西普瑟說，他經常收到主動發來的電子郵件，要求他審查一些證明P不等於NP的新嘗試——或者更糟糕的是，相反的嘗試。
儘管P與NP問題仍然未解決，但許多複雜性研究人員仍然認為它有一天會得到解決。“我從來沒有真正放棄它，”西普瑟說。他聲稱自己仍然時不時地拿出紙筆來研究它——幾乎是為了消遣，就像狗啃它最喜歡的骨頭一樣。畢竟，P與NP問題本身就是一個NP問題：找到答案的唯一方法就是不斷搜尋。雖然這個答案可能永遠不會出現，但如果出現，當我們看到它時就會知道。