P/NP問題50年：基礎理論舉步維艱，但AI正在不可能中尋找可能_風聞
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！36分钟前
1. 至2021年，P/NP問題已經50歲了，但其解決方案仍遙不可及。儘管算法與硬件的卓越進步使我們可以解決許多NP完全問題，但在密碼系統的破解方面仍進展甚微。
2. 隨着我們持續地在機器學習以及以數據為中心的計算領域取得激動人心的進步，P/NP問題向我們提供了一個寶貴的視角，去了解在未來的機器學習領域什麼是可能的，什麼是不可能的。
3. 雖然P/NP問題一開始涉及複雜問題的計算求解，但如今我們將其視為繪製這個領域未來發展藍圖的一種方法。
（編者注：正文內參考文獻序號為原文標註；原文發表於2022年。）
撰文 | Lance Fortnow（伊利諾斯理工學院計算機學院教授）
翻譯 | 許釗箐
1971年5月4日，數學家、計算機科學家史蒂夫·庫克（Steve Cook）在他的論文《定理證明過程的複雜性》（The Complexity of Theorem Proving Procedures）中向世人介紹了P/NP問題。如今，50多年過去了，全世界仍在嘗試解決這一問題。在2009年，我在《ACM通訊》（Communications of the ACM）雜誌上發表綜述文章《P/NP問題的現狀》，探討過這一話題[13]。
自2009年那篇文章發表以來，P/NP問題及其相關的理論並沒有顯著的進展，但是計算領域無疑發生了鉅變。雲計算的發展促進了社交網絡、智能手機、零工經濟、金融科技、空間計算、在線教育等領域的進步，並且也許其中最重要的是數據科學與機器學習的崛起。在2009年，市值排名前十名的公司中僅僅只包含一家大型科技公司：微軟。而截止至2020年9月，市值排名前七名的公司是：蘋果（Apple）、微軟（Microsoft）、亞馬遜（Amazon）、谷歌（Alphabet）、阿里巴巴（Alibaba）、臉書（Facebook）、騰訊（Tencent）[38]。在此期間，美國計算機科學專業畢業生的數量增加了兩倍多[8]，但仍遠遠不能滿足崗位的需求。
在本文中，我選擇通過P/NP問題的視角來看待計算、優化以及機器學習領域的進展，而不僅僅是簡單修改或更新2009年文章的內容。我們將關注這些進展是如何使我們更接近P=NP的世界，P/NP問題至今仍存在的侷限性，以及已經湧現的新的研究機會。特別地，我會探討我們是如何走向一個我稱之為“Optiland”的世界，在那裏我們幾乎可以奇蹟般地獲得P=NP的許多優點，並且同時避免一些缺點，比如打破密碼學的相關理論。
作為一個開放的數學難題，P/NP問題至今是其中最重要的之一；它被列入克萊數學研究所的千禧年大獎難題之一[21]（該組織為其中每一個問題的求解提供100萬美元的獎金）。在本文的最後，我也將陳述一些前沿計算機科學的相關理論結果。雖然這些結果沒有讓我們更接近於解決P/NP問題，但它們向我們展示了對於P/NP問題的思索仍然推動了該領域眾多的重要研究。
P/NP 問題
是否存在300個Facebook用户彼此之間都是好友的關係？你將如何為這個問題提供一個解答？假設你在Facebook公司工作，可以訪問公司所有數據，瞭解哪些用户是好友關係。你現在需要設計一個算法來尋找彼此都是好友並且人數足夠多的朋友羣體（Clique）。你可以先嚐試搜索所有滿足條件的300人朋友羣體，但由於實際人數過多，無法全部搜索。你也可以選擇一些更明智的方法，比如先嚐試搜索一些小型朋友羣體，之後再小的羣體合併為更大的羣體，但你會發現你所做的似乎都不起作用。事實上，沒有人知道比遍歷所有朋友羣體明顯更快的搜索方法，同時我們也不知道更快的方法是否不存在。
這基本上就是P/NP問題。NP代表我們可以高效檢驗其解答的問題。如果我告知你有300人可能形成了一個滿足條件的團體，你可以相對較快地檢驗他們彼此之間形成的44850對用户是否都是好友關係。上文的分團問題（Clique problem）便是一個NP問題。而P則表示我們可以高效地找到解的問題。對於分團問題，我們不知道它是否在P問題這個集合中。或許會令你驚訝的是，分團問題有一個被稱為NP完備（NP-complete）的性質——即當且僅當P=NP時，我們才可以高效地解決分團問題。許多其他問題也有這一性質，比如三着色問題（一副地圖能否可以僅被三種顏色着色使得任意相鄰的兩個國家擁有不同的顏色？），旅行商問題（在眾多的城市中找到一個最短路線，使得商人訪問每座城市一次並回到初始的位置），以及其他成千上萬的問題。
嚴格地來説，P表示“多項式時間”（polynomial time），對應一類求解時間是以輸入長度為自變量的固定多項式的問題。而NP表示“非確定性多項式時間”（nondeterministic polynomial time），對應一類非確定性圖靈機可以不可思議地選擇出最佳答案的問題。在本文中，讀者可以把P和NP簡單地看作可高效求解的問題以及可高效驗證的問題。
如果讀者希望對於P/NP問題的重要性有更深入的非專業討論，可以閲讀我2009年的綜述文章[13]或者我在2013年基於這篇綜述文章寫作的科普書籍[14]。對於更專業的介紹，由邁克爾·加里（Michael Garey）和大衞·約翰遜（David Johnson）[16]在1979年創作的專著對於需要理解哪些問題是NP完備問題的讀者非常合適。這本專著至今仍然是這方面的寶貴參考資料。
為什麼我們現在談論P/NP問題？
1971年一個週二的下午，在美國俄亥俄州謝克海茨市的斯托弗薩默塞特酒店，史蒂芬·庫克（Stephen Cook）在ACM計算理論專題研討會上向與會者展示了他的論文，他證明了布爾表達式可滿足性問題（Boolean Satisfiability Problem）是NP完備的，並且證明了重言式問題（Tautology）是NP困難（NP-hard）的[10]。這些定理也表明，重言式問題是一個不在P集合中不錯的候選，並且我認為花費相當大的精力來嘗試證明這個猜想是值得的。這樣的證明將會是複雜性理論的重大突破。
與一個數學概念“約會”幾乎總是一個挑戰，歷史上也許還有很多P/NP問題可能的誕生時間。算法和證明的基本概念可以被追溯到古希臘時期，但據我們所知，P/NP這樣一般性的問題他們從未考慮過。高效計算與非確定性的理論基礎是在20世紀60年代發展起來的，而P/NP問題在此之前就形成了，只是我們不知道具體時間而已。
在1956年庫爾特·哥德爾（Kurt Gödel）寫給約翰·馮·諾伊曼（John von Neumann）的一封信中，哥德爾本質性地描述了P/NP問題。目前我們尚不清楚，當時身受癌症侵襲的馮·諾伊曼是否閲讀了這封信。直到1988年，這封信才被人們發現，並廣為傳播。而P/NP問題是直到理查德·卡爾普（Richard Karp）1972年發表論文[23]指出大量著名組合問題（包括分團問題、三着色問題、以及旅行商問題）是NP完備的之後才真正成為一種現象。1973年，當時在蘇聯的列昂尼德·萊文（Leonid Levin）在其1971年獨立研究的基礎上發表了一篇論文，其中定義了P/NP問題[27]。而當萊文的論文傳到西方的時候，P/NP問題已經成為計算領域最重要的問題了。
樂觀之地（Optiland）
在1995年的一篇經典論文中[20]，拉塞爾·因帕利亞佐（Russell Impagliazzo）描述了對於P/NP問題擁有不同程度可能性的五個世界：
1. 算法世界（Algorithmica）：P=NP或者某種理論上的等價，比如NP問題的快速隨機算法。
2. 啓發世界（Heuristica）: 在最壞的情況下NP問題很難求解，但是通常情況下求解是容易的。
3. 悲觀世界（Pessiland；譯者注：引申自拉丁語悲觀主義pessimus）：我們可以輕易地構建難以求解的NP問題，但是很難構建我們知道解答的NP問題。這是所有可能性中最壞的，因為在這個世界中，我們既不能在通常情況下解決困難的問題，也不能由這些問題的難度獲得任何明顯的加密優勢。
4. 單向加密世界（Minicrypt）：單向加密函數存在，但是我們沒有公開密鑰加密算法。
5. 加密狂歡世界（Cryptomania）: 公開密鑰加密是可能的，也就是説，雙方可以通過公開的信道交換加密信息。
這些對應不同情況的不同世界特意沒有被正式定義。根據我們對於P/NP問題的瞭解，它們表明了未知的各種可能性。人們通常認為（不是全體統一地），我們生活在可以“加密狂歡”的世界裏。
因帕利亞佐從P/NP的理論中總結出：“魚與熊掌不可兼得（You can’t have it all）”。我們可以求解困難的NP問題，或者可以擁有密碼學，兩者必有其一，但不會共存。不過，或許我們正在前往一個現實中的“樂觀之地”（Optiland；譯者注：與pessiland對應，引申自Optimum）。機器學習和軟件與硬件優化的進展，使我們能夠對於此前長期被認為是困難或不可能的問題取得進展，比如語音識別與蛋白質摺疊等問題，並且在大多數情況下我們的加密協議仍然是安全的。
在我2009年的綜述文章[13] “如果P=NP會怎麼樣？”章節裏，我當時寫道，“通過使用奧卡姆剃刀原則（Occam’s razor），學習變得容易了——我們只需尋找與數據一致的最簡單的方法”。近乎完美的視覺識別、語言理解、翻譯，以及所有其他的學習任務都變得容易解決。我們也將更好地預測天氣、地震以及其他自然現象。
如今，我們可以通過面部掃描來解鎖智能手機，通過詢問手機問題得到通常較為理想的回覆，也可以將我們的問題翻譯為另一種語言。智能手機會接收關於天氣和極端氣候的警報，而其預測能力比我們十幾年前想象的要好得多。同時，除了小長度密鑰加密會受到類似暴力破解的攻擊之外，密碼學理論基本沒有被撼動。接下來，讓我們來看一看計算、優化以及學習領域最近的進展是如何將我們領入“樂觀之地”的。
困難問題的求解
2016年，比爾·庫克（Bill Cook, 與前文中的史蒂夫·庫克沒有關係）和他的同事們決定迎接這項挑戰[9]：如何使用最短的路程到訪英國的每一家酒吧？他們列出了24727家酒吧的名單，並確定了最後的酒吧旅行路線——一次總長度45495239米的徒步旅行。這一距離比繞地球一圈還要長一些。
實際上，庫克對該問題做了一些簡化：他忽略了一些酒吧使得該問題有一個合適的規模。在一些英國媒體進行報道[7]之後，許多人抱怨名單中沒有他們最愛的酒吧。因此庫克團隊重新整理了一份包含49687家酒吧的名單，而新的行程長度是63739687米（見下圖）。與之前的路徑相比，人們只需要多走40%的路程，便能到訪數量是之前兩倍多的酒吧。這個酒吧旅行的問題與旅行商問題（最著名的NP完備問題之一）是等價的。到訪49687家酒吧所有可能路線的數量大約是“3後面跟着211761個0”。當然庫克的電腦不會遍歷所有路線，他們使用了各種優化技術。更令人印象深刻的是，這份路線還附帶一份基於線性規劃對偶性的最優性證明。
庫克團隊也承擔了一個更大的任務——尋找一條穿越200多萬恆星的最短路徑，其中恆星之間的距離可以被計算。他們獲得的路線總長度為28884456秒差距（譯者注：1秒差距約為3.26光年），和理論最佳值相比只有683秒差距的差別。
除了旅行商問題，我們在求解布爾可滿足性問題和混合整數規劃問題（Mixed-integer programming question）領域也取得了重大進展——一種線性規劃方法的變體，其中一些變量（不一定是全部）必須是整數。通過使用高度精煉的啓發式方法、高速處理器、專業硬件以及分佈式雲計算，人們基本已經可以解決實踐中出現的具有數以萬計的變量和數十萬甚至上百萬的約束的問題。
面對需要求解的NP問題，人們通常會將問題轉述為布爾可滿足性問題或混合整數規劃問題，進而使用最好的求解器求解。這些工具已經被成功地應用在電路與編碼的驗證與自動化測試、計算生物學、系統安全、產品與包裝設計、金融交易中，甚至用於求解困難的數學問題。
數據科學與機器學習
如今，任何《ACM通訊雜誌》的讀者和其他大多數人都不會忽視機器學習帶來的變革性影響，尤其是通過神經網絡實現的機器學習。使用人工神經元（籠統地講，計算加權閾值函數）實現建模計算的概念可以追溯到20世紀40年代沃倫·麥卡洛克（Warren McCulloch）和沃爾特·皮茨（Walter Pitts）[28]的研究。在20世紀90年代，約書亞·本希奧（Yoshua Bengio）、傑弗裏·辛頓（Geoffrey Hinton）和楊立昆（Yann LeCun）[26]提出了反向傳播等算法，為多層神經網絡學習訓練的發展奠定了基礎。更快、更廣泛的分佈式計算、專業硬件和海量數據也幫助並推動了機器學習的發展，使得它可以非常出色地完成眾多原本需要人類完成的任務。計算機協會（the Association for Computing Machinery，ACM）也為本希奧、辛頓和立昆授予了2018年的圖靈獎，以表彰他們的工作對人類社會產生的深遠影響。
那麼，機器學習與P/NP問題有什麼聯繫？（在本節中，當我們提及P=NP，它表示所有的NP問題在實踐中都有相關的高效算法。）奧卡姆剃刀原則指出，“如無必要，勿增實體”，或者説，最簡單的解釋可能才是正確的。如果P=NP，我們可以利用這一思想來建立一個強大的學習算法：找到一個與數據一致的最小的迴路。但即便可能沒有P=NP這個結論，機器學習也可以近似地實現這種方法，從而賦予了神經網絡驚人的能力。然而，神經網絡不太可能是那個“最小的”迴路。如今使用深度學習技術訓練的神經網絡往往結構是固定的，其參數與網絡中的權重有關。為了擁有足夠的表達能力，人們通常需要設置數百萬甚至更多的權重參數。而數量眾多的參數限制了神經網絡的能力：它們可以很好地進行面部識別，但是卻無法根據示例來學習如何進行乘法運算。
通用分佈（Universal distribution）和GPT-3 讓我們考慮任意長度二進制字符串的分佈。儘管均勻分佈是明顯不合理的，但是我們是否可以構建分佈使得任意相同長度的字符串擁有相同的概率？實際上，有些字符串確實會比其他的更重要。比如，π的前100萬位數字比隨機生成一個100萬位數字更有意義。因此或許你會希望給更有意義的字符串設置更高的概率。實現這一目標的方法很多，而實際上存在一個接近於任何其他可計算分佈的通用分佈（讀者可以參考科爾什赫等人的文章[25]）。通用分佈與學習訓練有很大的聯繫，例如，任意以小誤差率學習這種分佈的算法將可以學習所有可以計算的分佈。可惜的是，即便P=NP，通用分佈也是不可計算的。不過，如果P=NP，我們仍然可以得到一些有用的東西——我們可以創建一個可高效計算的分佈，使得它對於其他可高效計算的分佈是通用的。
我們能從機器學習中獲得什麼？以GPT（Generative Pre-trained Transformer，生成式預訓練轉換器）為例，特別是2020年發佈的GPT-3[5]。GPT-3從儘可能多的書面語料庫中提取了4100億個標記，進而訓練了1750億個參數。它可以回答問題，可以根據提示書寫文章，甚至可以生成代碼。儘管它還有漫長的優化之路要走，但是它已經可以像人類一樣創造內容，並因此受到好評。我們可以把GPT-3看作是一種分佈，並考慮算法輸出對應的概率——即一個弱版本的通用分佈。如果我們以一個給定的前綴限制通用分佈，那麼它就提供一個由該前綴提示的隨機樣本。GPT-3也可以基於這樣的提示，無需進一步訓練就能處理極大範圍的相關領域知識。隨着這方面研究的進展，我們也將越來越接近一個通用度量標準並從中實現內置式學習：基於給定上下文生成一個隨機的例子。
科學與醫藥 在科學世界，我們已經通過大規模模擬取得了眾多進展，比如探索核聚變反應。研究者們使用一種科學方法的範式：首先對於物理系統建立假設；然後使用模型進行預測；再用實驗模擬檢驗該預測，而不是直接實現核聚變反應。如果測試結果與預期不同，再修改或推翻這個模型並重復以上的過程。
在我們擁有一個有説服力的模型之後，我們可以在現實反應堆中進行一些昂貴的實驗測試。如果P=NP，像上文提及的，我們可以使用奧卡姆剃刀理論來建立假説——找到一個與數據一致的最小回路。機器學習的技巧可以緊接着沿着這個思路自動地創建假設。不管數據是來自於模擬、實驗還是傳感器，機器學習都可以創建出匹配數據的模型。然後我們可以使用這些模型來進行預測，並像前文提到過的那樣檢驗做出的預測。
儘管機器學習可以幫助我們找到未發現的假設和模型，但所獲得的結果未必是正確的。我們通常可以接受有95%置信水平的假設（這意味在20個不合格的假設中，有一個可能會被接受）。機器學習與數據科學的工具為我們生成假設的同時，也帶來了結果不符合事實的風險。醫學研究人員，特別是試圖解決癌症等疾病的研究人員，常常遇到算法上的阻礙，因為生物系統極其複雜。我們知道DNA構成一種編碼，它描述了我們的身體如何形成以及身體不同部分的功能，但我們對其運作原理知之甚少。
2020年11月30日，谷歌的DeepMind公司發佈了AlphaFold——一種基於氨基酸序列預測蛋白質結構的新算法[22]。AlphaFold的預測準確度幾乎達到了人工實驗的水平，即通過實驗構建氨基酸序列並測試其生成的蛋白質結構。雖然關於DeepMind是否真的“解決”了蛋白質摺疊的問題仍存爭議，並且現在便評估其影響力還為時過早，但從長遠來看，它為我們提供了一個新的數字化工具來研究蛋白質，理解它們是如何相互作用，並學習如何設計蛋白質來對抗疾病。
P/NP之外：象棋與圍棋 NP問題就像解謎遊戲。數獨問題就是NP完備的：在一個任意大小的宮格上，給定一些初始數字，然後求解其餘空格中數字。但是對於兩位玩家輪流執子的回合制遊戲，比如象棋和圍棋，如果我們想知道誰會在給定棋局下獲勝，情況又會怎麼樣呢？事實上，即便是P=NP，我們也未必可以找到完美的棋類算法。我們不得不考慮對於黑子的每一步，白子都可以走出合適的一步，並不斷循環直到白棋勝利。而設計這種交替的算法僅僅依靠P=NP是不夠的。這一類遊戲的算法設計被稱為PSPACE-hard——在沒有時間限制下，使用合理的存儲容量進行計算是困難的。根據具體的規則設定，象棋和圍棋的算法設計會更有難度。（感興趣的讀者可以閲讀德邁納與赫恩的文章[11]。）
不過，這並不意味着在假設P=NP的前提下，我們不能找到一個好的棋類算法。你可能做出一個大小合適的高效計算機程序，使其優於所有比它體量略小的高效程序。另一方面，即便沒有P=NP這一假設，計算機在棋類方面已經足夠強大。在1997年，IBM的超級電腦“深藍”擊敗了當時的國際象棋世界冠軍加里·卡斯帕羅夫（Gary Kasparov），然而在當時，即便是與有實力的業餘選手的對決，圍棋程序也難以取勝。在這之後，機器學習在計算機遊戲的算法設計方面取得了巨大的進步。讓我們直接跳過這段悠久的歷史，來看看2017年DeepMind開發的AlphaZero[35]。
AlphaZero使用了一種被稱為蒙特卡洛樹搜索（MCTS）的技術——讓雙方玩家隨機地落子從而決定最佳的棋路方案。AlphaZero使用深度學習來預測棋局的最佳分佈，以優化使用MCTS獲勝的機會。雖然AlphaZero並不是第一個使用MCTS的程序，但是它沒有任何內置策略或者訪問之前的棋類數據庫——它僅僅假設了遊戲的規則。這也使得AlphaZero在國際象棋和圍棋上都表現得出色，這兩種遊戲除了交替回合制和固定大小的棋盤之外截然不同。DeepMind最近進一步地研究了MuZero[33]——它甚至沒有完整的規則，僅僅有一些棋盤位置的表示，一系列符合規則的落子，以及哪些情況是贏、輸或者平局。現在我們已經明白，在國際象棋和圍棋中，純粹的機器學習可以很輕易地擊敗人類或者其他算法。而人為地干預只會妨礙它。對於象棋和圍棋這類遊戲，即便P=NP不足以解決這類問題，但機器學習卻可以取得成功。
可解釋的人工智能 很多機器學習算法似乎已經都運行得很好，但是我們卻不理解為什麼。如果你去觀察為了語音識別而訓練的神經網絡，你通常會難以理解它為何做出這樣的選擇。我們為什麼要關心這個問題呢？以下是一些原因：
1. 置信：我們如何知道神經網絡運行正確？除了檢查輸入和輸出，我們不會做其他任何的分析。不同的應用場景會有不同的置信水平：Netflix推薦了一部水平不高的電影沒什麼關係，但如果是自動駕駛的汽車選擇了一個錯誤的轉彎，結果就很嚴重。
2. 公平：有很多例子表明，通過數據訓練的算法受到了數據中有意或無意的偏差的影響。如果我們不理解程序，我們如何發現這些數據中的偏差？
3. 安全：如果使用機器學習來監管安全系統，我們將不知道哪些漏洞仍然存在，特別是當我們的敵手是不斷變化的時候。但如果我們理解代碼，我們就可以發現並修補安全漏洞。當然，如果敵手獲得了代碼，他們也可以發現漏洞。
4. 因果關係：目前我們最多隻能檢查機器學習算法是否與我們想要的輸出類型相關。理解代碼可以幫助我們理解數據中的因果關係，從而在科學與醫學方面取得新的進步。
如果P=NP，我們會得到一個更好的情況嗎？如果我們有一個NP完全問題的快速算法，你可以將其用於匹配問題或旅行商問題，找到可能的最小回路，但你不會知道為什麼這個迴路是對的。另一方面，我們想要一個可解釋算法的原因是我們希望可以理解它的性質，但如果P=NP，我們可以直接導出這些性質。現在研究可解釋的人工智能會議湧現出來，例如ACM FAccT會議。
機器學習的侷限性 雖然在過去十年中，機器學習已經展現了許多令人驚奇的結果，但很多系統還遠未達到完美的水平，在大多數應用場景中，人類仍然更勝一籌。人們也將繼續通過新的優化算法、數據收集與專業硬件來提高機器學習的能力。不過，機器學習似乎確實有其侷限性。正如我們上文提到過的，機器學習讓我們一定程度的接近P=NP，但卻永遠無法替代P=NP——機器學習在密碼破解方面進展甚微，我們也將在本文後面看到這一點。
機器學習似乎無法學習簡單的算術——例如對大量的數字求和或者大數之間相乘。人們可以想到將機器學習與符號運算的數學工具結合起來。然而，儘管在定理證明方面我們取得了一些令人矚目的進展[19]，但這與我們期待中的實際科研任務仍距離遙遠，即選取一篇科研文章，文中證明還未正式完成，使用AI系統補充細節並檢驗證明。
而P=NP將使這些任務變得簡單，或者至少易於處理。機器學習在面對不屬於其訓練分佈的任務時可能表現不佳。但這可能是概率較低的極端情況，例如訓練數據中並未獲得很好代表某個種族的人臉識別；或者可能是一種對抗性的嘗試——通過對輸入進行微小的更改來強行獲得不同的輸出，比如把停車標誌修改幾個像素，從而讓算法將其識別為一個限速標誌[12]。深度神經網絡算法可能有數百萬個參數，因此它們在分佈之外的泛化效果可能不理想。如果P=NP，我們可以獲得最小尺寸的模型從而有望實現更好的泛化，但如果沒有相應的實驗，我們永遠也無法驗證。
儘管機器學習令人印象深刻，但我們還沒有獲得任何接近於通用人工智能的東西——這個術語指的是對於一個主題有真正的理解，或是實現真正的意識或自我認知的人工系統。定義這些術語可能是棘手的、有爭議的，甚至是不可能的。於我個人而言，我從未見到過一個關於意識的正式定義，能夠體現我對於意識的直觀認識。我懷疑即使P=NP，我們也永遠無法實現強意義下的通用人工智能。
密碼學
雖然我們在解決NP問題方面取得了很大進展，但是密碼學的多種理論，包括單向函數（one-way functions）、安全散列算法（secure hashes）以及公鑰密碼學似乎都完好無損。如果NP問題存在一個高效的算法，那麼除了那些在信息學上安全的密碼系統，比如一次性密碼簿和一些基於量子物理學的密碼系統，其他所有密碼系統都會被破解。我們已經見證了很多成功的網絡安全攻擊，但它們通常源於糟糕的代碼漏洞、很弱的隨機數生成器或者人為疏漏，很少是因為密碼學理論的問題。
現在大多數CPU芯片都內置了AES（Advanced Encryption Standard），因此一旦我們使用了公鑰加密系統設置私鑰，我們就可以像發送普通文本一樣輕鬆地發送加密後的數據。加密技術為區塊鏈和加密貨幣的發展提供了動力，這意味着人們對於加密技術的信任足以讓他們願意把貨幣換成比特。邁克爾·卡恩斯（Michael Kearns）和萊斯利·瓦利安特（Leslie Valiant）在1994年證明[24]，如果可以學習到最小的迴路，甚至只是學到了最小的有界層的神經網絡，那麼它們就可以被用來分解質因數並破解公鑰加密系統。而到目前為止，機器學習算法還從未成功破解過加密協議，不過也沒有人期望機器學習算法可以成功。
為什麼我們在許多其他NP問題取得了進展，而加密系統仍可以表現良好？在密碼學中，我們可以選擇問題，特別是可以將其設計成難以計算並可被廣為測試的。而其他的NP問題通常來自應用問題或自然界。它們往往不是最困難的，也更容易折服於當下技術。
量子計算似乎威脅着當下保護我們互聯網交易的公鑰加密協議。秀爾算法（Shor’s algorithm）[34]可以進行質因數分解與其他數論計算。這種憂慮可以通過幾種方式來緩和。儘管量子計算取得了一些令人印象深刻的進展，但要開發出能處理足夠多糾纏比特的量子計算機，從而在一定規模上實現秀爾算法，我們可能仍需要幾十年甚至幾個世紀的時間。此外，研究者們也在開發可抵抗量子攻擊的公鑰密碼系統並取得了一定的進展。更多量子計算內容我們將在後文詳細討論。
我們不知道因式分解問題是否是NP完備的，所以即便我們沒有大規模的量子計算機，數學上的突破也有可能會帶來高效的算法。但無論你對量子領域的未來有什麼樣的看法，如果擁有多種方法來優化公鑰加密系統，它們可能都會派上用場。
如摩擦力般的複雜性
我們可以從計算複雜性中獲得什麼？此時，密碼學可能會從你的腦海浮現。但或許就像存在摩擦力一樣，宇宙使得某些計算很困難是有原因的。在物理世界中，克服摩擦力通常以消耗能量為代價，但是如果沒有摩擦力，我們寸步難行。在計算世界中，錯綜複雜的計算一般會使計算過程緩慢而低效，但如果沒有複雜性，就像沒有摩擦力一樣，我們也會有很多其他的問題。而P=NP在很多情況下，會讓我們消除“摩擦力”。
計算領域的最新進展表明，消除“摩擦力”有時會產生負面影響。例如人們不能直接閲讀別人思想，只能看到其採取的行動。經濟學家有一個術語，“偏好揭示”（preference revelation），旨在根據人們的行為來確定其偏好。在過去，由於缺乏數據與足夠的算力，這一領域一直被認為最多隻是非常不精確的一種藝術。
而如今，我們已經收集到了相當可觀的數據——來自人們的網絡搜索、相片與視頻、網購記錄、虛擬與現實世界中的訪問記錄、社交媒體上的活動等等。而且，機器學習可以處理這些龐雜的信息，並對人們的行為做出異常精確的預測。如今，計算機比我們更瞭解我們自己。
我們甚至已經有足夠的技術製作一副眼鏡，戴上它就可以讓我們瞭解對面人的名字、興趣與愛好，甚至其政治立場。因此這種信息上的複雜性已不再賦予我們隱私。人們需要依賴法律和企業責任來保護隱私。
計算上的“摩擦力”不僅體現在隱私這一方面。在1978年，美國政府解除了對航空公司的定價管制，但如果想要找到一條航線的最佳價格，人們往往需要給多家航空公司打電話諮詢，或者通過旅行社代理購票，當然旅行社也並不總是有動力去尋找最低的價格。因此航空公司致力於打造聲譽，一些公司側重優質的服務，另一些公司可以提供更低的價格。今天，我們可以很容易地找到最便宜的航班，因此航空公司在價格這個單一維度上投入了相當大的努力，他們通過計算優化定價並以犧牲飛行體驗的代價來安排座位。
這種“摩擦力”在以前也有助於打擊學生的作弊行為。在上世紀80年代，我讀大學時必須計算作答的微積分問題，現在已經可以被Mathematica軟件輕鬆解決。在我的入門理論課程中，我在為學生準備作業與考題的時候遇到了麻煩——答案都可以在網上找到。隨着GPT-3和其後續版本能力日益強大，甚至連論文與代碼都可以自動生成，如果GPT這類的工具已經可以解決對於學生來説最複雜的問題，我們要如何激發學生？
股票交易過去是在現場進行的，交易員用手勢來進行價格匹配。如今，交易算法自動地調整以適應新的價格，偶爾會導致價格瞬間暴跌。機器學習技術的發展已經引領了決策系統、人臉識別，將社交媒體內容與用户，還有司法判決進行大規模匹配。這些決策系統帶來了一些好的改變，但也為我們帶來了重大的挑戰，比如放大偏見、加劇政治上的兩極分化[30]。本文不詳細探討這個話題。
以上提到的這些只是許多可能的場景中的一小部分。作為計算機科學家，我們的目標是使計算儘可能的高效和簡單，但我們也必須牢記減少“摩擦力”的代價。
量子計算機的能力
隨着摩爾定律的極限越來越明顯，計算機科學家們已經將目光投向非傳統的計算模型以追尋下一階段的突破。這促進了量子計算理論與應用的發展。大型科技公司，如谷歌、微軟和IBM，還有一大批初創公司，都已在量子計算機開發上投入了大量資源。美國已經啓動了國家量子計劃（National Quantum Initiative），其他國家，尤其是中國，也都加入了這一行列。
2019年，谷歌[1]宣佈其使用了一台擁有53個量子比特的量子計算機實現了“量子遙遙領先”，解決了當前傳統計算無法解決的計算任務。儘管有些人質疑這一説法，但我們確實正處在量子計算新時代的邊緣。然而我們還遠沒有達到實現皮特·秀爾（Peter Shor）算法[34]所需要的數萬個量子比特的水平，從而解決當今計算機計算質因數分解問題。通常來説，量子計算被描述為由比特表示的狀態數，比如53量子比特的機器有253個狀態。這似乎表明，我們可以使用量子計算通過創建足夠多的狀態來解決NP完全問題——例如，在一個圖結構中，檢驗所有可能滿足條件的團體。可惜的是，量子算法操控這些狀態是受限的，而且所有的證據都表明，除了由格羅弗（Grover）算法[18]給出的二次加速改善，量子計算機無法解決NP完備問題[3]。
複雜性的進展
自2009年我發表那篇綜述文章之後，我們在理解高效計算能力方面取得了幾項重大進步。雖然這些結果對於解決P/NP問題沒有帶來顯著的進展，但依舊展現了它們是如何繼續啓發後續優秀研究的。
圖同構：一些NP問題可能既不是P（高效可解），也不是NP完備的（像分團問題一樣難）。其中我們前文提及的最著名的質因數分解問題，仍然需要指數級的時間來求解。而對於另一個類似的問題——圖同構問題，我們最近見證了激動人心的進展。圖同構指的是在重新標號的意義下，兩個圖是否相同。以Facebook為例，給定兩個千人的羣組，我們能否將名字在兩個羣組中以一種方式相互對應，並保持人們之間的好友關係？
20世紀80年代發表的與交互性證明相關的結果為證明圖同構不是NP完備的提供了強有力的證據[4]。而且即便是簡單的啓發式算法通常也可以快速解決這類問題。可是我們仍然缺乏一個適用於所有情況的多項式時間的圖同構算法。對於該問題，拉斯洛·巴拜（László Babai）
在2016年取得了突破性成果[2]，他提出了一種圖同構的擬多項式時間的算法。
電路設計：如果在完備的基（與門、或門、非門）下，小型電路不能求解NP問題，則P≠NP。雖然上世紀80年代有很多關於電路複雜度的研究成果問世，但它們都沒能接近於證明P≠NP。2009年的綜述文章指出，在此前的20年裏，電路複雜性領域沒有取得新的重大成果。這種情況一直持續到2010年。1987年，拉茲波洛夫（Razborov）[32]和斯莫倫斯基（Smolensky）[36]證明了對於固定素數p對應的常數深度電路——由取餘電路（Modp）、與門、或門、非門電路組成——是不可能計算大多數函數的。不過，如果是有6對應的取餘電路（Mod6），存在少量的一些證明工作。但即使是證明NEXP（一種NP的指數時間版本）不能被常數深度的、由與或非門電路以及6對應的取餘電路組成的小型電路計算這一問題，其仍在幾十年中未被解決。因此常數深度的電路被認為在計算上能力很弱。在這方面工作的缺乏也反映了我們在闡釋計算模型侷限性這一領域取得的進展十分有限。
在2010年，瑞恩·威廉姆斯（Ryan Williams）[39]證明了NEXP確實不能被常數深度、由6對應的取餘電路或任意其他取餘電路的小型電路計算求解。他構造了一種新技術，應用了可滿足性算法。這種算法比嘗試所有賦值並使用幾種複雜工具來獲得下界要好一些。後來，威廉姆斯和他的學生科迪·默裏（Cody Murray）[29]在此結果上更進一步，證明了即便是不確定的擬多項式時間的算法，也不存在對應的常數深度的、帶有固定m對應的取餘電路（Modm）的小型電路。然而證明不存在任意深度的小型電路可以求解NP問題（這正是證明P≠NP所需要的）仍然遙不可及。
複雜性的反擊：在2009年的綜述文章中，有一節題為“新希望”[13]。在這一節中，我們基於克坦·穆穆利（Ketan Mulmuley）和米林德·索霍尼（Milind Sohoni）提出的代數幾何與表示理論，討論了一種新的幾何複雜性理論來攻破P/NP問題。簡而言之，穆穆利和索霍尼試圖構造高維多邊形，以體現代數形式的NP問題的性質，並表明它具有任意與P問題的代數性質相對應多邊形不同的性質。他們的猜想之一是認為多邊形包含某種表示論的結構。然而在2016年，彼得·布爾吉瑟（Peter Bürgisser），克里斯蒂安·艾肯邁爾（Christian Ikenmeyer），和格蕾塔·帕諾娃（Greta Panova）[6]證明這種方法不會成功。
儘管布爾吉瑟、艾肯邁爾、與帕諾娃的工作否定了幾何複雜性理論（GCT）區分P與NP問題的可能，人們仍然有可能根據表示論結構的數量構造不同的多邊形。只不過我們不再應該期待GCT理論可以在不久的將來解決P/NP問題。
不可能的可能性
當我們思考P/NP問題時，我們發現它有許多不同的含義。P/NP是正式定義的、長時間懸而未決、仍有百萬美元懸賞的一個數學問題。在本文中，我們看到通過可計算性理論、電路設計、證明和代數幾何等工具試圖解決P/NP問題的努力。目前我們還沒有一種強有力的方法解決P/NP問題。甚至從某種意義上説，我們到解決這個問題的距離比以前任何時候都要遠。
還有一些NP問題是我們希望或需要解決的。在1976年的經典文獻《計算機與難解性：一本NP完備性理論的指南》中[16]，加里（Garey）與約翰遜（Johnson）舉了一個例子：一位倒黴的員工被要求解決一個NP完備的優化問題。最後這位員工找到老闆説：“我找不到一個高效的算法，但這世界上的天才名流也一樣找不到。“言外之意是老闆不應該解僱這位員工，因為僱傭其他人也無法解決這個問題。
在P/NP問題的研究早期，我們將NP完備性看作一種障礙——這些問題是我們無法解決的。但隨着計算機與算法的發展，人們發現通過啓發式算法、近似算法和暴力計算的結合，我們也可以在NP問題上取得進展。在加里和約翰遜的故事中，如果我是老闆，我不會解僱這位員工，而是建議嘗試使用混合整數規劃、機器學習或者暴力搜索等方法。NP完備意味着不可能的時代已經過去了。現在NP完備僅僅意味着可能沒有一種算法可以永遠有效和可擴展。
在我2013年關於P/NP問題的書中[14]，有一章名為“美麗的世界”。在這一章中，我想象了一個理想化的世界：一位捷克數學家在這個世界中證明了P=NP，從而得出一個對於所有的NP問題都非常高效的算法。儘管我們現在沒有，也很可能永遠不會生活在這樣理想的世界，但是隨着我們在計算上一步一步地前進，我們已經實現了很多醫學進步，打造出與現實難以區分的虛擬世界，發明出創造新藝術作品的機器學習算法，P=NP所帶來的美妙或沒那麼美妙的結果似乎不再遙不可及。
我們正走在幾乎完全顛覆P/NP問題的意義的道路上。與其將其認為是一種障礙，不如將P/NP問題看作一扇為我們指引方向，展現不可能中的可能性的大門。
致謝
感謝喬希·格羅喬（Josh Grochow）與我對GCT問題非常有幫助的討論，以及庫克允許我們使用相關圖片。同樣感謝喬希以及審稿人對於本文的建議與幫助。本文的一些材料改編自作者的博客。
本文經作者授權發表於《返樸》，原文譯自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
1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。
版權説明：歡迎個人轉發，任何形式的媒體或機構未經授權，不得轉載和摘編。轉載授權請在「返樸」微信公眾號內聯繫後台。