核心觀點：

1. 至2021年，P/NP問題已經(jīng)50歲了，但其解決方案仍遙不可及。盡管算法與硬件的卓越進步使我們可以解決許多NP完全問題，但在密碼系統(tǒng)的破解方面仍進展甚微。

2. 隨著我們持續(xù)地在機器學(xué)習(xí)以及以數(shù)據(jù)為中心的計算領(lǐng)域取得激動人心的進步，P/NP問題向我們提供了一個寶貴的視角，去了解在未來的機器學(xué)習(xí)領(lǐng)域什么是可能的，什么是不可能的。

3. 雖然P/NP問題一開始涉及復(fù)雜問題的計算求解，但如今我們將其視為繪制這個領(lǐng)域未來發(fā)展藍圖的一種方法。

（編者注：正文內(nèi)參考文獻序號為原文標(biāo)注；原文發(fā)表于2022年。）

撰文 | Lance Fortnow（伊利諾斯理工學(xué)院計算機學(xué)院教授）

翻譯 | 許釗箐

1971年5月4日，數(shù)學(xué)家、計算機科學(xué)家史蒂夫·庫克（Steve Cook）在他的論文《定理證明過程的復(fù)雜性》（The Complexity of Theorem Proving Procedures）中向世人介紹了P/NP問題。如今，50多年過去了，全世界仍在嘗試解決這一問題。在2009年，我在《ACM通訊》（Communications of the ACM）雜志上發(fā)表綜述文章《P/NP問題的現(xiàn)狀》，探討過這一話題[13]。

自2009年那篇文章發(fā)表以來，P/NP問題及其相關(guān)的理論并沒有顯著的進展，但是計算領(lǐng)域無疑發(fā)生了巨變。云計算的發(fā)展促進了社交網(wǎng)絡(luò)、智能手機、零工經(jīng)濟、金融科技、空間計算、在線教育等領(lǐng)域的進步，并且也許其中最重要的是數(shù)據(jù)科學(xué)與機器學(xué)習(xí)的崛起。在2009年，市值排名前十名的公司中僅僅只包含一家大型科技公司：微軟。而截止至2020年9月，市值排名前七名的公司是：蘋果（Apple）、微軟（Microsoft）、亞馬遜（Amazon）、谷歌（Alphabet）、阿里巴巴（Alibaba）、臉書（Facebook）、騰訊（Tencent）[38]。在此期間，美國計算機科學(xué)專業(yè)畢業(yè)生的數(shù)量增加了兩倍多[8]，但仍遠(yuǎn)遠(yuǎn)不能滿足崗位的需求。

在本文中，我選擇通過P/NP問題的視角來看待計算、優(yōu)化以及機器學(xué)習(xí)領(lǐng)域的進展，而不僅僅是簡單修改或更新2009年文章的內(nèi)容。我們將關(guān)注這些進展是如何使我們更接近P=NP的世界，P/NP問題至今仍存在的局限性，以及已經(jīng)涌現(xiàn)的新的研究機會。特別地，我會探討我們是如何走向一個我稱之為“Optiland”的世界，在那里我們幾乎可以奇跡般地獲得P=NP的許多優(yōu)點，并且同時避免一些缺點，比如打破密碼學(xué)的相關(guān)理論。

作為一個開放的數(shù)學(xué)難題，P/NP問題至今是其中最重要的之一；它被列入克萊數(shù)學(xué)研究所的千禧年大獎難題之一[21]（該組織為其中每一個問題的求解提供100萬美元的獎金）。在本文的最后，我也將陳述一些前沿計算機科學(xué)的相關(guān)理論結(jié)果。雖然這些結(jié)果沒有讓我們更接近于解決P/NP問題，但它們向我們展示了對于P/NP問題的思索仍然推動了該領(lǐng)域眾多的重要研究。

P/NP 問題

是否存在300個Facebook用戶彼此之間都是好友的關(guān)系？你將如何為這個問題提供一個解答？假設(shè)你在Facebook公司工作，可以訪問公司所有數(shù)據(jù)，了解哪些用戶是好友關(guān)系。你現(xiàn)在需要設(shè)計一個算法來尋找彼此都是好友并且人數(shù)足夠多的朋友群體（Clique）。你可以先嘗試搜索所有滿足條件的300人朋友群體，但由于實際人數(shù)過多，無法全部搜索。你也可以選擇一些更明智的方法，比如先嘗試搜索一些小型朋友群體，之后再小的群體合并為更大的群體，但你會發(fā)現(xiàn)你所做的似乎都不起作用。事實上，沒有人知道比遍歷所有朋友群體明顯更快的搜索方法，同時我們也不知道更快的方法是否不存在。

這基本上就是P/NP問題。NP代表我們可以高效檢驗其解答的問題。如果我告知你有300人可能形成了一個滿足條件的團體，你可以相對較快地檢驗他們彼此之間形成的44850對用戶是否都是好友關(guān)系。上文的分團問題（Clique problem）便是一個NP問題。而P則表示我們可以高效地找到解的問題。對于分團問題，我們不知道它是否在P問題這個集合中?；蛟S會令你驚訝的是，分團問題有一個被稱為NP完備（NP-complete）的性質(zhì)——即當(dāng)且僅當(dāng)P=NP時，我們才可以高效地解決分團問題。許多其他問題也有這一性質(zhì)，比如三著色問題（一副地圖能否可以僅被三種顏色著色使得任意相鄰的兩個國家擁有不同的顏色？），旅行商問題（在眾多的城市中找到一個最短路線，使得商人訪問每座城市一次并回到初始的位置），以及其他成千上萬的問題。

嚴(yán)格地來說，P表示“多項式時間”（polynomial time），對應(yīng)一類求解時間是以輸入長度為自變量的固定多項式的問題。而NP表示“非確定性多項式時間”（nondeterministic polynomial time），對應(yīng)一類非確定性圖靈機可以不可思議地選擇出最佳答案的問題。在本文中，讀者可以把P和NP簡單地看作可高效求解的問題以及可高效驗證的問題。

如果讀者希望對于P/NP問題的重要性有更深入的非專業(yè)討論，可以閱讀我2009年的綜述文章[13]或者我在2013年基于這篇綜述文章寫作的科普書籍[14]。對于更專業(yè)的介紹，由邁克爾·加里（Michael Garey）和大衛(wèi)·約翰遜（David Johnson）[16]在1979年創(chuàng)作的專著對于需要理解哪些問題是NP完備問題的讀者非常合適。這本專著至今仍然是這方面的寶貴參考資料。

為什么我們現(xiàn)在談?wù)揚/NP問題？

1971年一個周二的下午，在美國俄亥俄州謝克海茨市的斯托弗薩默塞特酒店，史蒂芬·庫克（Stephen Cook）在ACM計算理論專題研討會上向與會者展示了他的論文，他證明了布爾表達式可滿足性問題（Boolean Satisfiability Problem）是NP完備的，并且證明了重言式問題（Tautology）是NP困難（NP-hard）的[10]。這些定理也表明，重言式問題是一個不在P集合中不錯的候選，并且我認(rèn)為花費相當(dāng)大的精力來嘗試證明這個猜想是值得的。這樣的證明將會是復(fù)雜性理論的重大突破。

與一個數(shù)學(xué)概念“約會”幾乎總是一個挑戰(zhàn)，歷史上也許還有很多P/NP問題可能的誕生時間。算法和證明的基本概念可以被追溯到古希臘時期，但據(jù)我們所知，P/NP這樣一般性的問題他們從未考慮過。高效計算與非確定性的理論基礎(chǔ)是在20世紀(jì)60年代發(fā)展起來的，而P/NP問題在此之前就形成了，只是我們不知道具體時間而已。

在1956年庫爾特·哥德爾（Kurt G?del）寫給約翰·馮·諾伊曼（John von Neumann）的一封信中，哥德爾本質(zhì)性地描述了P/NP問題。目前我們尚不清楚，當(dāng)時身受癌癥侵襲的馮·諾伊曼是否閱讀了這封信。直到1988年，這封信才被人們發(fā)現(xiàn)，并廣為傳播。而P/NP問題是直到理查德·卡爾普（Richard Karp）1972年發(fā)表論文[23]指出大量著名組合問題（包括分團問題、三著色問題、以及旅行商問題）是NP完備的之后才真正成為一種現(xiàn)象。1973年，當(dāng)時在蘇聯(lián)的列昂尼德·萊文（Leonid Levin）在其1971年獨立研究的基礎(chǔ)上發(fā)表了一篇論文，其中定義了P/NP問題[27]。而當(dāng)萊文的論文傳到西方的時候，P/NP問題已經(jīng)成為計算領(lǐng)域最重要的問題了。

樂觀之地（Optiland）

在1995年的一篇經(jīng)典論文中[20]，拉塞爾·因帕利亞佐（Russell Impagliazzo）描述了對于P/NP問題擁有不同程度可能性的五個世界：

1. 算法世界（Algorithmica）：P=NP或者某種理論上的等價，比如NP問題的快速隨機算法。

2. 啟發(fā)世界（Heuristica）: 在最壞的情況下NP問題很難求解，但是通常情況下求解是容易的。

3. 悲觀世界（Pessiland；譯者注：引申自拉丁語悲觀主義pessimus）：我們可以輕易地構(gòu)建難以求解的NP問題，但是很難構(gòu)建我們知道解答的NP問題。這是所有可能性中最壞的，因為在這個世界中，我們既不能在通常情況下解決困難的問題，也不能由這些問題的難度獲得任何明顯的加密優(yōu)勢。

4. 單向加密世界（Minicrypt）：單向加密函數(shù)存在，但是我們沒有公開密鑰加密算法。

5. 加密狂歡世界（Cryptomania）: 公開密鑰加密是可能的，也就是說，雙方可以通過公開的信道交換加密信息。

這些對應(yīng)不同情況的不同世界特意沒有被正式定義。根據(jù)我們對于P/NP問題的了解，它們表明了未知的各種可能性。人們通常認(rèn)為（不是全體統(tǒng)一地），我們生活在可以“加密狂歡”的世界里。

因帕利亞佐從P/NP的理論中總結(jié)出：“魚與熊掌不可兼得（You can't have it all）”。我們可以求解困難的NP問題，或者可以擁有密碼學(xué)，兩者必有其一，但不會共存。不過，或許我們正在前往一個現(xiàn)實中的“樂觀之地”（Optiland；譯者注：與pessiland對應(yīng)，引申自O(shè)ptimum）。機器學(xué)習(xí)和軟件與硬件優(yōu)化的進展，使我們能夠?qū)τ诖饲伴L期被認(rèn)為是困難或不可能的問題取得進展，比如語音識別與蛋白質(zhì)折疊等問題，并且在大多數(shù)情況下我們的加密協(xié)議仍然是安全的。

在我2009年的綜述文章[13]?“如果P=NP會怎么樣？”章節(jié)里，我當(dāng)時寫道，“通過使用奧卡姆剃刀原則（Occam’s razor），學(xué)習(xí)變得容易了——我們只需尋找與數(shù)據(jù)一致的最簡單的方法”。近乎完美的視覺識別、語言理解、翻譯，以及所有其他的學(xué)習(xí)任務(wù)都變得容易解決。我們也將更好地預(yù)測天氣、地震以及其他自然現(xiàn)象。

如今，我們可以通過面部掃描來解鎖智能手機，通過詢問手機問題得到通常較為理想的回復(fù)，也可以將我們的問題翻譯為另一種語言。智能手機會接收關(guān)于天氣和極端氣候的警報，而其預(yù)測能力比我們十幾年前想象的要好得多。同時，除了小長度密鑰加密會受到類似暴力破解的攻擊之外，密碼學(xué)理論基本沒有被撼動。接下來，讓我們來看一看計算、優(yōu)化以及學(xué)習(xí)領(lǐng)域最近的進展是如何將我們領(lǐng)入“樂觀之地”的。

困難問題的求解

2016年，比爾·庫克（Bill Cook, 與前文中的史蒂夫·庫克沒有關(guān)系）和他的同事們決定迎接這項挑戰(zhàn)[9]：如何使用最短的路程到訪英國的每一家酒吧？他們列出了24727家酒吧的名單，并確定了最后的酒吧旅行路線——一次總長度45495239米的徒步旅行。這一距離比繞地球一圈還要長一些。

實際上，庫克對該問題做了一些簡化：他忽略了一些酒吧使得該問題有一個合適的規(guī)模。在一些英國媒體進行報道[7]之后，許多人抱怨名單中沒有他們最愛的酒吧。因此庫克團隊重新整理了一份包含49687家酒吧的名單，而新的行程長度是63739687米（見下圖）。與之前的路徑相比，人們只需要多走40%的路程，便能到訪數(shù)量是之前兩倍多的酒吧。這個酒吧旅行的問題與旅行商問題（最著名的NP完備問題之一）是等價的。到訪49687家酒吧所有可能路線的數(shù)量大約是“3后面跟著211761個0”。當(dāng)然庫克的電腦不會遍歷所有路線，他們使用了各種優(yōu)化技術(shù)。更令人印象深刻的是，這份路線還附帶一份基于線性規(guī)劃對偶性的最優(yōu)性證明。

穿過49687家英國酒吧的最短路線 圖片來源：math.uwaterloo.ca/tsp/uk

庫克團隊也承擔(dān)了一個更大的任務(wù)——尋找一條穿越200多萬恒星的最短路徑，其中恒星之間的距離可以被計算。他們獲得的路線總長度為28884456秒差距（譯者注：1秒差距約為3.26光年），和理論最佳值相比只有683秒差距的差別。

除了旅行商問題，我們在求解布爾可滿足性問題和混合整數(shù)規(guī)劃問題（Mixed-integer programming question）領(lǐng)域也取得了重大進展——一種線性規(guī)劃方法的變體，其中一些變量（不一定是全部）必須是整數(shù)。通過使用高度精煉的啟發(fā)式方法、高速處理器、專業(yè)硬件以及分布式云計算，人們基本已經(jīng)可以解決實踐中出現(xiàn)的具有數(shù)以萬計的變量和數(shù)十萬甚至上百萬的約束的問題。

面對需要求解的NP問題，人們通常會將問題轉(zhuǎn)述為布爾可滿足性問題或混合整數(shù)規(guī)劃問題，進而使用最好的求解器求解。這些工具已經(jīng)被成功地應(yīng)用在電路與編碼的驗證與自動化測試、計算生物學(xué)、系統(tǒng)安全、產(chǎn)品與包裝設(shè)計、金融交易中，甚至用于求解困難的數(shù)學(xué)問題。

數(shù)據(jù)科學(xué)與機器學(xué)習(xí)

如今，任何《ACM通訊雜志》的讀者和其他大多數(shù)人都不會忽視機器學(xué)習(xí)帶來的變革性影響，尤其是通過神經(jīng)網(wǎng)絡(luò)實現(xiàn)的機器學(xué)習(xí)。使用人工神經(jīng)元（籠統(tǒng)地講，計算加權(quán)閾值函數(shù)）實現(xiàn)建模計算的概念可以追溯到20世紀(jì)40年代沃倫·麥卡洛克（Warren McCulloch）和沃爾特·皮茨（Walter Pitts）[28]的研究。在20世紀(jì)90年代，約書亞·本希奧（Yoshua Bengio）、杰弗里·辛頓（Geoffrey Hinton）和楊立昆（Yann LeCun）[26]提出了反向傳播等算法，為多層神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)訓(xùn)練的發(fā)展奠定了基礎(chǔ)。更快、更廣泛的分布式計算、專業(yè)硬件和海量數(shù)據(jù)也幫助并推動了機器學(xué)習(xí)的發(fā)展，使得它可以非常出色地完成眾多原本需要人類完成的任務(wù)。計算機協(xié)會（the Association for Computing Machinery，ACM）也為本希奧、辛頓和立昆授予了2018年的圖靈獎，以表彰他們的工作對人類社會產(chǎn)生的深遠(yuǎn)影響。

那么，機器學(xué)習(xí)與P/NP問題有什么聯(lián)系？（在本節(jié)中，當(dāng)我們提及P=NP，它表示所有的NP問題在實踐中都有相關(guān)的高效算法。）奧卡姆剃刀原則指出，“如無必要，勿增實體”，或者說，最簡單的解釋可能才是正確的。如果P=NP，我們可以利用這一思想來建立一個強大的學(xué)習(xí)算法：找到一個與數(shù)據(jù)一致的最小的回路。但即便可能沒有P=NP這個結(jié)論，機器學(xué)習(xí)也可以近似地實現(xiàn)這種方法，從而賦予了神經(jīng)網(wǎng)絡(luò)驚人的能力。然而，神經(jīng)網(wǎng)絡(luò)不太可能是那個“最小的”回路。如今使用深度學(xué)習(xí)技術(shù)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)往往結(jié)構(gòu)是固定的，其參數(shù)與網(wǎng)絡(luò)中的權(quán)重有關(guān)。為了擁有足夠的表達能力，人們通常需要設(shè)置數(shù)百萬甚至更多的權(quán)重參數(shù)。而數(shù)量眾多的參數(shù)限制了神經(jīng)網(wǎng)絡(luò)的能力：它們可以很好地進行面部識別，但是卻無法根據(jù)示例來學(xué)習(xí)如何進行乘法運算。

通用分布（Universal distribution）和GPT-3?讓我們考慮任意長度二進制字符串的分布。盡管均勻分布是明顯不合理的，但是我們是否可以構(gòu)建分布使得任意相同長度的字符串擁有相同的概率？實際上，有些字符串確實會比其他的更重要。比如，π的前100萬位數(shù)字比隨機生成一個100萬位數(shù)字更有意義。因此或許你會希望給更有意義的字符串設(shè)置更高的概率。實現(xiàn)這一目標(biāo)的方法很多，而實際上存在一個接近于任何其他可計算分布的通用分布（讀者可以參考科爾什赫等人的文章[25]）。通用分布與學(xué)習(xí)訓(xùn)練有很大的聯(lián)系，例如，任意以小誤差率學(xué)習(xí)這種分布的算法將可以學(xué)習(xí)所有可以計算的分布?？上У氖?，即便P=NP，通用分布也是不可計算的。不過，如果P=NP，我們?nèi)匀豢梢缘玫揭恍┯杏玫臇|西——我們可以創(chuàng)建一個可高效計算的分布，使得它對于其他可高效計算的分布是通用的。

我們能從機器學(xué)習(xí)中獲得什么？以GPT（Generative Pre-trained Transformer，生成式預(yù)訓(xùn)練轉(zhuǎn)換器）為例，特別是2020年發(fā)布的GPT-3[5]。GPT-3從盡可能多的書面語料庫中提取了4100億個標(biāo)記，進而訓(xùn)練了1750億個參數(shù)。它可以回答問題，可以根據(jù)提示書寫文章，甚至可以生成代碼。盡管它還有漫長的優(yōu)化之路要走，但是它已經(jīng)可以像人類一樣創(chuàng)造內(nèi)容，并因此受到好評。我們可以把GPT-3看作是一種分布，并考慮算法輸出對應(yīng)的概率——即一個弱版本的通用分布。如果我們以一個給定的前綴限制通用分布，那么它就提供一個由該前綴提示的隨機樣本。GPT-3也可以基于這樣的提示，無需進一步訓(xùn)練就能處理極大范圍的相關(guān)領(lǐng)域知識。隨著這方面研究的進展，我們也將越來越接近一個通用度量標(biāo)準(zhǔn)并從中實現(xiàn)內(nèi)置式學(xué)習(xí)：基于給定上下文生成一個隨機的例子。

科學(xué)與醫(yī)藥?在科學(xué)世界，我們已經(jīng)通過大規(guī)模模擬取得了眾多進展，比如探索核聚變反應(yīng)。研究者們使用一種科學(xué)方法的范式：首先對于物理系統(tǒng)建立假設(shè)；然后使用模型進行預(yù)測；再用實驗?zāi)M檢驗該預(yù)測，而不是直接實現(xiàn)核聚變反應(yīng)。如果測試結(jié)果與預(yù)期不同，再修改或推翻這個模型并重復(fù)以上的過程。

在我們擁有一個有說服力的模型之后，我們可以在現(xiàn)實反應(yīng)堆中進行一些昂貴的實驗測試。如果P=NP，像上文提及的，我們可以使用奧卡姆剃刀理論來建立假說——找到一個與數(shù)據(jù)一致的最小回路。機器學(xué)習(xí)的技巧可以緊接著沿著這個思路自動地創(chuàng)建假設(shè)。不管數(shù)據(jù)是來自于模擬、實驗還是傳感器，機器學(xué)習(xí)都可以創(chuàng)建出匹配數(shù)據(jù)的模型。然后我們可以使用這些模型來進行預(yù)測，并像前文提到過的那樣檢驗做出的預(yù)測。

盡管機器學(xué)習(xí)可以幫助我們找到未發(fā)現(xiàn)的假設(shè)和模型，但所獲得的結(jié)果未必是正確的。我們通?？梢越邮苡?5%置信水平的假設(shè)（這意味在20個不合格的假設(shè)中，有一個可能會被接受）。機器學(xué)習(xí)與數(shù)據(jù)科學(xué)的工具為我們生成假設(shè)的同時，也帶來了結(jié)果不符合事實的風(fēng)險。醫(yī)學(xué)研究人員，特別是試圖解決癌癥等疾病的研究人員，常常遇到算法上的阻礙，因為生物系統(tǒng)極其復(fù)雜。我們知道DNA構(gòu)成一種編碼，它描述了我們的身體如何形成以及身體不同部分的功能，但我們對其運作原理知之甚少。

2020年11月30日，谷歌的DeepMind公司發(fā)布了AlphaFold——一種基于氨基酸序列預(yù)測蛋白質(zhì)結(jié)構(gòu)的新算法[22]。AlphaFold的預(yù)測準(zhǔn)確度幾乎達到了人工實驗的水平，即通過實驗構(gòu)建氨基酸序列并測試其生成的蛋白質(zhì)結(jié)構(gòu)。雖然關(guān)于DeepMind是否真的“解決”了蛋白質(zhì)折疊的問題仍存爭議，并且現(xiàn)在便評估其影響力還為時過早，但從長遠(yuǎn)來看，它為我們提供了一個新的數(shù)字化工具來研究蛋白質(zhì)，理解它們是如何相互作用，并學(xué)習(xí)如何設(shè)計蛋白質(zhì)來對抗疾病。

P/NP之外：象棋與圍棋?NP問題就像解謎游戲。數(shù)獨問題就是NP完備的：在一個任意大小的宮格上，給定一些初始數(shù)字，然后求解其余空格中數(shù)字。但是對于兩位玩家輪流執(zhí)子的回合制游戲，比如象棋和圍棋，如果我們想知道誰會在給定棋局下獲勝，情況又會怎么樣呢？事實上，即便是P=NP，我們也未必可以找到完美的棋類算法。我們不得不考慮對于黑子的每一步，白子都可以走出合適的一步，并不斷循環(huán)直到白棋勝利。而設(shè)計這種交替的算法僅僅依靠P=NP是不夠的。這一類游戲的算法設(shè)計被稱為PSPACE-hard——在沒有時間限制下，使用合理的存儲容量進行計算是困難的。根據(jù)具體的規(guī)則設(shè)定，象棋和圍棋的算法設(shè)計會更有難度。（感興趣的讀者可以閱讀德邁納與赫恩的文章[11]。）

不過，這并不意味著在假設(shè)P=NP的前提下，我們不能找到一個好的棋類算法。你可能做出一個大小合適的高效計算機程序，使其優(yōu)于所有比它體量略小的高效程序。另一方面，即便沒有P=NP這一假設(shè)，計算機在棋類方面已經(jīng)足夠強大。在1997年，IBM的超級電腦“深藍”擊敗了當(dāng)時的國際象棋世界冠軍加里·卡斯帕羅夫（Gary Kasparov），然而在當(dāng)時，即便是與有實力的業(yè)余選手的對決，圍棋程序也難以取勝。在這之后，機器學(xué)習(xí)在計算機游戲的算法設(shè)計方面取得了巨大的進步。讓我們直接跳過這段悠久的歷史，來看看2017年DeepMind開發(fā)的AlphaZero[35]。

AlphaZero使用了一種被稱為蒙特卡洛樹搜索（MCTS）的技術(shù)——讓雙方玩家隨機地落子從而決定最佳的棋路方案。AlphaZero使用深度學(xué)習(xí)來預(yù)測棋局的最佳分布，以優(yōu)化使用MCTS獲勝的機會。雖然AlphaZero并不是第一個使用MCTS的程序，但是它沒有任何內(nèi)置策略或者訪問之前的棋類數(shù)據(jù)庫——它僅僅假設(shè)了游戲的規(guī)則。這也使得AlphaZero在國際象棋和圍棋上都表現(xiàn)得出色，這兩種游戲除了交替回合制和固定大小的棋盤之外截然不同。DeepMind最近進一步地研究了MuZero[33]——它甚至沒有完整的規(guī)則，僅僅有一些棋盤位置的表示，一系列符合規(guī)則的落子，以及哪些情況是贏、輸或者平局。現(xiàn)在我們已經(jīng)明白，在國際象棋和圍棋中，純粹的機器學(xué)習(xí)可以很輕易地?fù)魯∪祟惢蛘咂渌惴ā６藶榈馗深A(yù)只會妨礙它。對于象棋和圍棋這類游戲，即便P=NP不足以解決這類問題，但機器學(xué)習(xí)卻可以取得成功。

可解釋的人工智能?很多機器學(xué)習(xí)算法似乎已經(jīng)都運行得很好，但是我們卻不理解為什么。如果你去觀察為了語音識別而訓(xùn)練的神經(jīng)網(wǎng)絡(luò)，你通常會難以理解它為何做出這樣的選擇。我們?yōu)槭裁匆P(guān)心這個問題呢？以下是一些原因：

1.?置信：我們?nèi)绾沃郎窠?jīng)網(wǎng)絡(luò)運行正確？除了檢查輸入和輸出，我們不會做其他任何的分析。不同的應(yīng)用場景會有不同的置信水平：Netflix推薦了一部水平不高的電影沒什么關(guān)系，但如果是自動駕駛的汽車選擇了一個錯誤的轉(zhuǎn)彎，結(jié)果就很嚴(yán)重。

2.?公平：有很多例子表明，通過數(shù)據(jù)訓(xùn)練的算法受到了數(shù)據(jù)中有意或無意的偏差的影響。如果我們不理解程序，我們?nèi)绾伟l(fā)現(xiàn)這些數(shù)據(jù)中的偏差？

3.?安全：如果使用機器學(xué)習(xí)來監(jiān)管安全系統(tǒng)，我們將不知道哪些漏洞仍然存在，特別是當(dāng)我們的敵手是不斷變化的時候。但如果我們理解代碼，我們就可以發(fā)現(xiàn)并修補安全漏洞。當(dāng)然，如果敵手獲得了代碼，他們也可以發(fā)現(xiàn)漏洞。

4.?因果關(guān)系：目前我們最多只能檢查機器學(xué)習(xí)算法是否與我們想要的輸出類型相關(guān)。理解代碼可以幫助我們理解數(shù)據(jù)中的因果關(guān)系，從而在科學(xué)與醫(yī)學(xué)方面取得新的進步。

如果P=NP，我們會得到一個更好的情況嗎？如果我們有一個NP完全問題的快速算法，你可以將其用于匹配問題或旅行商問題，找到可能的最小回路，但你不會知道為什么這個回路是對的。另一方面，我們想要一個可解釋算法的原因是我們希望可以理解它的性質(zhì)，但如果P=NP，我們可以直接導(dǎo)出這些性質(zhì)?，F(xiàn)在研究可解釋的人工智能會議涌現(xiàn)出來，例如ACM FAccT會議。

機器學(xué)習(xí)的局限性?雖然在過去十年中，機器學(xué)習(xí)已經(jīng)展現(xiàn)了許多令人驚奇的結(jié)果，但很多系統(tǒng)還遠(yuǎn)未達到完美的水平，在大多數(shù)應(yīng)用場景中，人類仍然更勝一籌。人們也將繼續(xù)通過新的優(yōu)化算法、數(shù)據(jù)收集與專業(yè)硬件來提高機器學(xué)習(xí)的能力。不過，機器學(xué)習(xí)似乎確實有其局限性。正如我們上文提到過的，機器學(xué)習(xí)讓我們一定程度的接近P=NP，但卻永遠(yuǎn)無法替代P=NP——機器學(xué)習(xí)在密碼破解方面進展甚微，我們也將在本文后面看到這一點。

機器學(xué)習(xí)似乎無法學(xué)習(xí)簡單的算術(shù)——例如對大量的數(shù)字求和或者大數(shù)之間相乘。人們可以想到將機器學(xué)習(xí)與符號運算的數(shù)學(xué)工具結(jié)合起來。然而，盡管在定理證明方面我們?nèi)〉昧艘恍┝钊瞬毮康倪M展[19]，但這與我們期待中的實際科研任務(wù)仍距離遙遠(yuǎn)，即選取一篇科研文章，文中證明還未正式完成，使用AI系統(tǒng)補充細(xì)節(jié)并檢驗證明。

而P=NP將使這些任務(wù)變得簡單，或者至少易于處理。機器學(xué)習(xí)在面對不屬于其訓(xùn)練分布的任務(wù)時可能表現(xiàn)不佳。但這可能是概率較低的極端情況，例如訓(xùn)練數(shù)據(jù)中并未獲得很好代表某個種族的人臉識別；或者可能是一種對抗性的嘗試——通過對輸入進行微小的更改來強行獲得不同的輸出，比如把停車標(biāo)志修改幾個像素，從而讓算法將其識別為一個限速標(biāo)志[12]。深度神經(jīng)網(wǎng)絡(luò)算法可能有數(shù)百萬個參數(shù)，因此它們在分布之外的泛化效果可能不理想。如果P=NP，我們可以獲得最小尺寸的模型從而有望實現(xiàn)更好的泛化，但如果沒有相應(yīng)的實驗，我們永遠(yuǎn)也無法驗證。

盡管機器學(xué)習(xí)令人印象深刻，但我們還沒有獲得任何接近于通用人工智能的東西——這個術(shù)語指的是對于一個主題有真正的理解，或是實現(xiàn)真正的意識或自我認(rèn)知的人工系統(tǒng)。定義這些術(shù)語可能是棘手的、有爭議的，甚至是不可能的。于我個人而言，我從未見到過一個關(guān)于意識的正式定義，能夠體現(xiàn)我對于意識的直觀認(rèn)識。我懷疑即使P=NP，我們也永遠(yuǎn)無法實現(xiàn)強意義下的通用人工智能。

密碼學(xué)

雖然我們在解決NP問題方面取得了很大進展，但是密碼學(xué)的多種理論，包括單向函數(shù)（one-way functions）、安全散列算法（secure hashes）以及公鑰密碼學(xué)似乎都完好無損。如果NP問題存在一個高效的算法，那么除了那些在信息學(xué)上安全的密碼系統(tǒng)，比如一次性密碼簿和一些基于量子物理學(xué)的密碼系統(tǒng)，其他所有密碼系統(tǒng)都會被破解。我們已經(jīng)見證了很多成功的網(wǎng)絡(luò)安全攻擊，但它們通常源于糟糕的代碼漏洞、很弱的隨機數(shù)生成器或者人為疏漏，很少是因為密碼學(xué)理論的問題。

現(xiàn)在大多數(shù)CPU芯片都內(nèi)置了AES（Advanced Encryption Standard），因此一旦我們使用了公鑰加密系統(tǒng)設(shè)置私鑰，我們就可以像發(fā)送普通文本一樣輕松地發(fā)送加密后的數(shù)據(jù)。加密技術(shù)為區(qū)塊鏈和加密貨幣的發(fā)展提供了動力，這意味著人們對于加密技術(shù)的信任足以讓他們愿意把貨幣換成比特。邁克爾·卡恩斯（Michael Kearns）和萊斯利·瓦利安特（Leslie Valiant）在1994年證明[24]，如果可以學(xué)習(xí)到最小的回路，甚至只是學(xué)到了最小的有界層的神經(jīng)網(wǎng)絡(luò)，那么它們就可以被用來分解質(zhì)因數(shù)并破解公鑰加密系統(tǒng)。而到目前為止，機器學(xué)習(xí)算法還從未成功破解過加密協(xié)議，不過也沒有人期望機器學(xué)習(xí)算法可以成功。

為什么我們在許多其他NP問題取得了進展，而加密系統(tǒng)仍可以表現(xiàn)良好？在密碼學(xué)中，我們可以選擇問題，特別是可以將其設(shè)計成難以計算并可被廣為測試的。而其他的NP問題通常來自應(yīng)用問題或自然界。它們往往不是最困難的，也更容易折服于當(dāng)下技術(shù)。

量子計算似乎威脅著當(dāng)下保護我們互聯(lián)網(wǎng)交易的公鑰加密協(xié)議。秀爾算法（Shor’s algorithm）[34]可以進行質(zhì)因數(shù)分解與其他數(shù)論計算。這種憂慮可以通過幾種方式來緩和。盡管量子計算取得了一些令人印象深刻的進展，但要開發(fā)出能處理足夠多糾纏比特的量子計算機，從而在一定規(guī)模上實現(xiàn)秀爾算法，我們可能仍需要幾十年甚至幾個世紀(jì)的時間。此外，研究者們也在開發(fā)可抵抗量子攻擊的公鑰密碼系統(tǒng)并取得了一定的進展。更多量子計算內(nèi)容我們將在后文詳細(xì)討論。

我們不知道因式分解問題是否是NP完備的，所以即便我們沒有大規(guī)模的量子計算機，數(shù)學(xué)上的突破也有可能會帶來高效的算法。但無論你對量子領(lǐng)域的未來有什么樣的看法，如果擁有多種方法來優(yōu)化公鑰加密系統(tǒng)，它們可能都會派上用場。

如摩擦力般的復(fù)雜性

我們可以從計算復(fù)雜性中獲得什么？此時，密碼學(xué)可能會從你的腦海浮現(xiàn)。但或許就像存在摩擦力一樣，宇宙使得某些計算很困難是有原因的。在物理世界中，克服摩擦力通常以消耗能量為代價，但是如果沒有摩擦力，我們寸步難行。在計算世界中，錯綜復(fù)雜的計算一般會使計算過程緩慢而低效，但如果沒有復(fù)雜性，就像沒有摩擦力一樣，我們也會有很多其他的問題。而P=NP在很多情況下，會讓我們消除“摩擦力”。

計算領(lǐng)域的最新進展表明，消除“摩擦力”有時會產(chǎn)生負(fù)面影響。例如人們不能直接閱讀別人思想，只能看到其采取的行動。經(jīng)濟學(xué)家有一個術(shù)語，“偏好揭示”（preference revelation），旨在根據(jù)人們的行為來確定其偏好。在過去，由于缺乏數(shù)據(jù)與足夠的算力，這一領(lǐng)域一直被認(rèn)為最多只是非常不精確的一種藝術(shù)。

而如今，我們已經(jīng)收集到了相當(dāng)可觀的數(shù)據(jù)——來自人們的網(wǎng)絡(luò)搜索、相片與視頻、網(wǎng)購記錄、虛擬與現(xiàn)實世界中的訪問記錄、社交媒體上的活動等等。而且，機器學(xué)習(xí)可以處理這些龐雜的信息，并對人們的行為做出異常精確的預(yù)測。如今，計算機比我們更了解我們自己。

我們甚至已經(jīng)有足夠的技術(shù)制作一副眼鏡，戴上它就可以讓我們了解對面人的名字、興趣與愛好，甚至其政治立場。因此這種信息上的復(fù)雜性已不再賦予我們隱私。人們需要依賴法律和企業(yè)責(zé)任來保護隱私。

計算上的“摩擦力”不僅體現(xiàn)在隱私這一方面。在1978年，美國政府解除了對航空公司的定價管制，但如果想要找到一條航線的最佳價格，人們往往需要給多家航空公司打電話咨詢，或者通過旅行社代理購票，當(dāng)然旅行社也并不總是有動力去尋找最低的價格。因此航空公司致力于打造聲譽，一些公司側(cè)重優(yōu)質(zhì)的服務(wù)，另一些公司可以提供更低的價格。今天，我們可以很容易地找到最便宜的航班，因此航空公司在價格這個單一維度上投入了相當(dāng)大的努力，他們通過計算優(yōu)化定價并以犧牲飛行體驗的代價來安排座位。

這種“摩擦力”在以前也有助于打擊學(xué)生的作弊行為。在上世紀(jì)80年代，我讀大學(xué)時必須計算作答的微積分問題，現(xiàn)在已經(jīng)可以被Mathematica軟件輕松解決。在我的入門理論課程中，我在為學(xué)生準(zhǔn)備作業(yè)與考題的時候遇到了麻煩——答案都可以在網(wǎng)上找到。隨著GPT-3和其后續(xù)版本能力日益強大，甚至連論文與代碼都可以自動生成，如果GPT這類的工具已經(jīng)可以解決對于學(xué)生來說最復(fù)雜的問題，我們要如何激發(fā)學(xué)生？

股票交易過去是在現(xiàn)場進行的，交易員用手勢來進行價格匹配。如今，交易算法自動地調(diào)整以適應(yīng)新的價格，偶爾會導(dǎo)致價格瞬間暴跌。機器學(xué)習(xí)技術(shù)的發(fā)展已經(jīng)引領(lǐng)了決策系統(tǒng)、人臉識別，將社交媒體內(nèi)容與用戶，還有司法判決進行大規(guī)模匹配。這些決策系統(tǒng)帶來了一些好的改變，但也為我們帶來了重大的挑戰(zhàn)，比如放大偏見、加劇政治上的兩極分化[30]。本文不詳細(xì)探討這個話題。

以上提到的這些只是許多可能的場景中的一小部分。作為計算機科學(xué)家，我們的目標(biāo)是使計算盡可能的高效和簡單，但我們也必須牢記減少“摩擦力”的代價。

量子計算機的能力

隨著摩爾定律的極限越來越明顯，計算機科學(xué)家們已經(jīng)將目光投向非傳統(tǒng)的計算模型以追尋下一階段的突破。這促進了量子計算理論與應(yīng)用的發(fā)展。大型科技公司，如谷歌、微軟和IBM，還有一大批初創(chuàng)公司，都已在量子計算機開發(fā)上投入了大量資源。美國已經(jīng)啟動了國家量子計劃（National Quantum Initiative），其他國家，尤其是中國，也都加入了這一行列。

2019年，谷歌[1]宣布其使用了一臺擁有53個量子比特的量子計算機實現(xiàn)了“量子遙遙領(lǐng)先”，解決了當(dāng)前傳統(tǒng)計算無法解決的計算任務(wù)。盡管有些人質(zhì)疑這一說法，但我們確實正處在量子計算新時代的邊緣。然而我們還遠(yuǎn)沒有達到實現(xiàn)皮特·秀爾（Peter Shor）算法[34]所需要的數(shù)萬個量子比特的水平，從而解決當(dāng)今計算機計算質(zhì)因數(shù)分解問題。通常來說，量子計算被描述為由比特表示的狀態(tài)數(shù)，比如53量子比特的機器有253個狀態(tài)。這似乎表明，我們可以使用量子計算通過創(chuàng)建足夠多的狀態(tài)來解決NP完全問題——例如，在一個圖結(jié)構(gòu)中，檢驗所有可能滿足條件的團體。可惜的是，量子算法操控這些狀態(tài)是受限的，而且所有的證據(jù)都表明，除了由格羅弗（Grover）算法[18]給出的二次加速改善，量子計算機無法解決NP完備問題[3]。

復(fù)雜性的進展

自2009年我發(fā)表那篇綜述文章之后，我們在理解高效計算能力方面取得了幾項重大進步。雖然這些結(jié)果對于解決P/NP問題沒有帶來顯著的進展，但依舊展現(xiàn)了它們是如何繼續(xù)啟發(fā)后續(xù)優(yōu)秀研究的。

圖同構(gòu)：一些NP問題可能既不是P（高效可解），也不是NP完備的（像分團問題一樣難）。其中我們前文提及的最著名的質(zhì)因數(shù)分解問題，仍然需要指數(shù)級的時間來求解。而對于另一個類似的問題——圖同構(gòu)問題，我們最近見證了激動人心的進展。圖同構(gòu)指的是在重新標(biāo)號的意義下，兩個圖是否相同。以Facebook為例，給定兩個千人的群組，我們能否將名字在兩個群組中以一種方式相互對應(yīng)，并保持人們之間的好友關(guān)系？

20世紀(jì)80年代發(fā)表的與交互性證明相關(guān)的結(jié)果為證明圖同構(gòu)不是NP完備的提供了強有力的證據(jù)[4]。而且即便是簡單的啟發(fā)式算法通常也可以快速解決這類問題?？墒俏覀?nèi)匀蝗狈σ粋€適用于所有情況的多項式時間的圖同構(gòu)算法。對于該問題，拉斯洛·巴拜（László Babai）

在2016年取得了突破性成果[2]，他提出了一種圖同構(gòu)的擬多項式時間的算法。

巴拜的證明是一份將組合學(xué)與群論結(jié)合的杰出工作。盡管讓算法在多項式時間內(nèi)運行結(jié)束仍需要很多新的突破，但巴拜給出了一個重要的理論結(jié)果，是P與NP完備之間最重要問題之一的重大進展。

電路設(shè)計：如果在完備的基（與門、或門、非門）下，小型電路不能求解NP問題，則P≠NP。雖然上世紀(jì)80年代有很多關(guān)于電路復(fù)雜度的研究成果問世，但它們都沒能接近于證明P≠NP。2009年的綜述文章指出，在此前的20年里，電路復(fù)雜性領(lǐng)域沒有取得新的重大成果。這種情況一直持續(xù)到2010年。1987年，拉茲波洛夫（Razborov）[32]和斯莫倫斯基（Smolensky）[36]證明了對于固定素數(shù)p對應(yīng)的常數(shù)深度電路——由取余電路（Modp）、與門、或門、非門電路組成——是不可能計算大多數(shù)函數(shù)的。不過，如果是有6對應(yīng)的取余電路（Mod6），存在少量的一些證明工作。但即使是證明NEXP（一種NP的指數(shù)時間版本）不能被常數(shù)深度的、由與或非門電路以及6對應(yīng)的取余電路組成的小型電路計算這一問題，其仍在幾十年中未被解決。因此常數(shù)深度的電路被認(rèn)為在計算上能力很弱。在這方面工作的缺乏也反映了我們在闡釋計算模型局限性這一領(lǐng)域取得的進展十分有限。

在2010年，瑞恩·威廉姆斯（Ryan Williams）[39]證明了NEXP確實不能被常數(shù)深度、由6對應(yīng)的取余電路或任意其他取余電路的小型電路計算求解。他構(gòu)造了一種新技術(shù)，應(yīng)用了可滿足性算法。這種算法比嘗試所有賦值并使用幾種復(fù)雜工具來獲得下界要好一些。后來，威廉姆斯和他的學(xué)生科迪·默里（Cody Murray）[29]在此結(jié)果上更進一步，證明了即便是不確定的擬多項式時間的算法，也不存在對應(yīng)的常數(shù)深度的、帶有固定m對應(yīng)的取余電路（Modm）的小型電路。然而證明不存在任意深度的小型電路可以求解NP問題（這正是證明P≠NP所需要的）仍然遙不可及。

復(fù)雜性的反擊：在2009年的綜述文章中，有一節(jié)題為“新希望”[13]。在這一節(jié)中，我們基于克坦·穆穆利（Ketan Mulmuley）和米林德·索霍尼（Milind Sohoni）提出的代數(shù)幾何與表示理論，討論了一種新的幾何復(fù)雜性理論來攻破P/NP問題。簡而言之，穆穆利和索霍尼試圖構(gòu)造高維多邊形，以體現(xiàn)代數(shù)形式的NP問題的性質(zhì)，并表明它具有任意與P問題的代數(shù)性質(zhì)相對應(yīng)多邊形不同的性質(zhì)。他們的猜想之一是認(rèn)為多邊形包含某種表示論的結(jié)構(gòu)。然而在2016年，彼得·布爾吉瑟（Peter Bürgisser），克里斯蒂安·艾肯邁爾（Christian Ikenmeyer），和格蕾塔·帕諾娃（Greta Panova）[6]證明這種方法不會成功。

盡管布爾吉瑟、艾肯邁爾、與帕諾娃的工作否定了幾何復(fù)雜性理論（GCT）區(qū)分P與NP問題的可能，人們?nèi)匀挥锌赡芨鶕?jù)表示論結(jié)構(gòu)的數(shù)量構(gòu)造不同的多邊形。只不過我們不再應(yīng)該期待GCT理論可以在不久的將來解決P/NP問題。

不可能的可能性

當(dāng)我們思考P/NP問題時，我們發(fā)現(xiàn)它有許多不同的含義。P/NP是正式定義的、長時間懸而未決、仍有百萬美元懸賞的一個數(shù)學(xué)問題。在本文中，我們看到通過可計算性理論、電路設(shè)計、證明和代數(shù)幾何等工具試圖解決P/NP問題的努力。目前我們還沒有一種強有力的方法解決P/NP問題。甚至從某種意義上說，我們到解決這個問題的距離比以前任何時候都要遠(yuǎn)。

還有一些NP問題是我們希望或需要解決的。在1976年的經(jīng)典文獻《計算機與難解性：一本NP完備性理論的指南》中[16]，加里（Garey）與約翰遜（Johnson）舉了一個例子：一位倒霉的員工被要求解決一個NP完備的優(yōu)化問題。最后這位員工找到老板說：“我找不到一個高效的算法，但這世界上的天才名流也一樣找不到?！把酝庵馐抢习宀粦?yīng)該解雇這位員工，因為雇傭其他人也無法解決這個問題。

在P/NP問題的研究早期，我們將NP完備性看作一種障礙——這些問題是我們無法解決的。但隨著計算機與算法的發(fā)展，人們發(fā)現(xiàn)通過啟發(fā)式算法、近似算法和暴力計算的結(jié)合，我們也可以在NP問題上取得進展。在加里和約翰遜的故事中，如果我是老板，我不會解雇這位員工，而是建議嘗試使用混合整數(shù)規(guī)劃、機器學(xué)習(xí)或者暴力搜索等方法。NP完備意味著不可能的時代已經(jīng)過去了?，F(xiàn)在NP完備僅僅意味著可能沒有一種算法可以永遠(yuǎn)有效和可擴展。

在我2013年關(guān)于P/NP問題的書中[14]，有一章名為“美麗的世界”。在這一章中，我想象了一個理想化的世界：一位捷克數(shù)學(xué)家在這個世界中證明了P=NP，從而得出一個對于所有的NP問題都非常高效的算法。盡管我們現(xiàn)在沒有，也很可能永遠(yuǎn)不會生活在這樣理想的世界，但是隨著我們在計算上一步一步地前進，我們已經(jīng)實現(xiàn)了很多醫(yī)學(xué)進步，打造出與現(xiàn)實難以區(qū)分的虛擬世界，發(fā)明出創(chuàng)造新藝術(shù)作品的機器學(xué)習(xí)算法，P=NP所帶來的美妙或沒那么美妙的結(jié)果似乎不再遙不可及。

我們正走在幾乎完全顛覆P/NP問題的意義的道路上。與其將其認(rèn)為是一種障礙，不如將P/NP問題看作一扇為我們指引方向，展現(xiàn)不可能中的可能性的大門。

致謝

感謝喬?！じ窳_喬（Josh Grochow）與我對GCT問題非常有幫助的討論，以及庫克允許我們使用相關(guān)圖片。同樣感謝喬希以及審稿人對于本文的建議與幫助。本文的一些材料改編自作者的博客。

參考文獻

[1] Arute, F., Arya, K., Babbus, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boxio, S., Brandao, F.G.S.L., Buell, D.A., et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505–510. https://doi.org/10.1038/s41586-019-1666-5

[2] Babai, L. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (2016), 684–697. https://doi.org/10.1145/2897518.2897542

[3] Bennett, C., Bernstein, E., Brassard, G., and Vazirani, U. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510–1523.

[4] Boppana, R., H?stad, J., and Zachos, S. Does co-NP have short interactive proofs? Information Processing Letters 25, 2 (1987), 127–132.

[5] Brown, T.B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D.M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Suskever, I., and Amodei, D. Language models are few-shot learners (2020). arXiv:2005.14165 [cs.CL]

[6] Bürgisser, P., Ikenmeyer, C., and Panova, G. No occurrence obstructions in geometric complexity theory. J. of the American Mathematical Society 32, 1 (2019), 163–193. https://doi.org/10.1090/jams/908

[7] Coldwell, W. World's longest pub crawl: Maths team plots route between 25,000 UK boozers. The Guardian (Oct. 21, 2016). https://www.theguardian.com/travel/2016/oct/21/worlds-longest-pub-crawlmaths-team-plots-route-between-every-pub-in-uk

[8] CRA Taulbee Survey. Computing Research Association (2020), https://cra.org/resources/taulbee-survey.

[9] Cook, B. Traveling salesman problem (2020), http://www.math.uwaterloo.ca/tsp/uk.

[10] Cook, S. The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium on the Theory of Computing (1971), 151–158.

[11] Demaine, E.D. and Hearn, R.A. Playing games with algorithms: Algorithmic combinatorial game theory. Games of No Chance 3: Mathematical Sciences Research Institute Publications, Vol. 56. Michael H. Albert and Richard J. Nowakowski (Eds.), Cambridge University Press (2009), 3–56. http://erikdemaine.org/papers/AlgGameTheory_GONC3/

[12] Eykholt, K., Evtimov, I., Fernandes, E., Li, B., Rahmati, A., Xiao, C., Prakash, A., Kohno, T., and Song, D. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (2018).

[13] Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 9 (Sept. 2009), 78–86. https://doi.org/10.1145/1562164.1562186

[14] Fortnow, L. The Golden Ticket: P, NP and the Search for the Impossible. Princeton University Press, Princeton, (2013). https://goldenticket.fortnow.com

[15] Fortnow, L and Gasarch, W. Computational Complexity. https://blog.computationalcomplexity.org

[16] Garey, M. and Johnson, D. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, (1979).

[17] G?del, K. Letter to John von Neumann. (1956). https://www2.karlin.mff.cuni.cz/~krajicek/goedel-letter.pdf

[18] Grover, L. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (1996), 212–219.

[19] Hartnett, K. Building the mathematical library of the future. Quanta Magazine (Oct. 1, 2020). https://www.quantamagazine.org/building-the-mathematical-library-of-the-future-20201001/.

[20] Impagliazzo, R. A personal view of average-case complexity theory. In Proceedings of the 10th Annual Conference on Structure in Complexity Theory. IEEE Computer Society Press (1995), 134–147. https://doi.org/10.1109/SCT.1995.514853

[21] Jaffe, A. The Millennium Grand Challenge in Mathematics. Notices of the AMS 53, 6 (June/July 2006), 652–660. http://www.ams.org/notices/200606/feajaffe.pdf

[22] Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Tunyasuvunakool, K., Ronneberger, O., Bates, R., ?ídek, A., Bridgland, A., Meyer, C., Kohl, S.A.A., Potapenko, A., Ballard, A.J., Cowie, A., Romera-Paredes B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen, S., Reiman, D., Steinegger, M., Pacholska, M., Silver, D., Vinyals, O., Senior, A.W., Kavukcuoglu, K., Kohli, P., and Hassabis, D. High accuracy protein structure prediction using deep learning. In 14th Critical Assessment of Techniques for Protein Structure Prediction (Abstract Book) (2020), 22–24. https://predictioncenter.org/casp14/doc/CASP14_Abstracts.pdf

[23] Karp, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher (Eds.). Plenum Press, New York, (1972), 85–103.

[24] Kearns, M. and Valiant, L. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM 41, 1 (Jan. 1994), 67–95. https://doi.org/10.1145/174644.174647

[25] Kirchherr, W., Li, M., and Vitányi, P. The miraculous universal distribution. The Mathematical Intelligencer 19, 4 (Sep. 1, 1997), 7–15. https://doi.org/10.1007/BF03024407

[26] LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature 521, 7553 (May 1, 2015), 436–444. https://doi.org/10.1038/nature14539

[27] Levin, L. Universal'ny?ie pereborny?ie zadachi (Universal search problems: in Russian). Problemy Peredachi Informatsii 9, 3 (1973), 265–266. Corrected English translation in.37

[28] McCulloch, W.S. and Pitts, W. A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics 5, 4 (Dec. 1, 1943), 115–133. https://doi.org/10.1007/BF02478259

[29] Murray, C. and Williams, R. Circuit lower bounds for nondeterministic quasi polytime: An easy witness Lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (2018), 890–901. https://doi.org/10.1145/3188745.3188910

[30] O'Neil, C. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy. Crown (2016), New York.

[31] Peikert, C. Lattice cryptography for the Internet. In Post-Quantum Cryptography, Michele Mosca (Ed.). Springer International Publishing, Cham (2014), 197–219.

[32] Razborov, A. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR 41, 4 (1987), 333–338.

[33] Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Laurent Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., and Silver, D. Mastering Atari, go, chess and shogi by planning with a learned model. Nature 588, 7839 (Dec. 1, 2020), 604–609. https://doi.org/10.1038/s41586-020-03051-4.

[34] Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484–1509.

[35] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362, 6419 (2018), 1140–1144. https://doi.org/10.1126/science.aar6404

[36] Smolensky, R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on the Theory of Computing (1987), 77–82.

[37] Trakhtenbrot, R. A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing 6, 4 (1984), 384–400.

[38]Wikipedia contributors. List of public corporations by market capitalization. Wikipedia, the Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=List_of_public_corporations_by_market_capitalization&oldid=1045945999.

[39] Williams, R. Nonuniform ACC circuit lower bounds. Journal of the ACM 61, 1, Article 2 (Jan. 2014). https://doi.org/10.1145/2559903.

本文經(jīng)作者授權(quán)發(fā)表于《返樸》，原文譯自Fortnow, Lance. "Fifty years of P vs. NP and the possibility of the impossible." Communications of the ACM 65.1 (2021): 76-85. DOI: 10.1145/3460351