P vs. NP 五十年：AI正在解決不可解問題

P和NP問題一直是計算機領域的老大難問題，那么在近50年間，人們對這個問題有什么深入的研究呢？讓我們在本文中深挖這個世紀難題。

作者 | Lance Fortnow

編譯 | Don

編輯 | 青暮

在1971年5月4日，偉大的計算機科學家和數學家Steve Cook就在他的論文《定理證明程序的復雜性 The Complexity of Theorem Proving Procedures》中首次向世界提出了P和NP的問題。在50年后的今天，世人仍然在試圖解決這個計算機領域中最著名的問題。其實在12年前（2009年），我也曾經就該問題進行了一些討論，大家可以看之前的《P與NP問題的現狀》綜述。

文章地址：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

計算機理論在近些年并沒有得到很大的發展。從2009年那篇文章發表以來，P與NP問題及其背后的理論并沒有發生顯著的變化，但計算世界確實發生了變化。比如說云計算，就推動了社交網絡、智能手機、經濟、金融科技、空間計算、在線教育等領域的飛速發展。更重要的是，云計算還幫助了數據科學和機器學習的崛起。

在2009年，世界前10大科技公司中出現了一家獨大的場面——微軟公司獨孤求敗。但是截至2020年9月，市值前七名的公司分別是蘋果、微軟、亞馬遜、Alphabet（谷歌）、阿里巴巴、Facebook和騰訊，彼此平分秋色。不光是大公司的變革明顯，計算機人才的需求量也是如此。據統計，在2009到2020年間，美國的計算機科學專業畢業生的數量增加了三倍有余，但這還是無法滿足市場上對該領域人才的需求量。

P和NP的問題作為數學界和計算機界的一個難題來源已久，它被列入克萊數學研究所的千年難題之一。而且這個組織還為能夠攻克該問題的研究人員提供了上百萬美元的獎金懸賞。我會在文章的末尾用一些例子來解釋P和NP問題，這雖然沒能讓我們從本質上對其有更多的認識，但是也能看出來P和NP的很多思考和成果推動了這個領域的研究和發展。

1

P和NP問題

如果有人問你，你能不能在微博上找到一些人，他們彼此之間都是朋友，這幫人的數量大概是300左右。你會怎么回答這個問題？

假如你在一個社交平臺企業工作，而且可以訪問整個平臺的數據庫，也就是能看到每個人的好友列表，那你可以嘗試遍歷所有的300人群組，然后挨個兒看他們是否有相同的關注人群，如果是，則他們被稱為一個團（Clique ）。但是這樣算法的計算量太大，數量也太多了，通常無法全部遍歷。

你也可以耍耍小聰明，也就是從小的群組開始，然后慢慢的將這個小群組擴大，納入那些彼此之間都是好友的人。當然實際做起來可能也有難度。其實從理論上來說，這個問題沒有最好的解決方案，沒有人知道到底存不存在比挨個遍歷更好的解決方案。

這個例子其實就是一個典型的P和NP的問題。NP代表了可以有效檢驗一個解的準確性的一類問題。比如當你知道有300個人可能構成一個團，你就可以快速的檢驗出由他們兩兩配對的44850對用戶到底是不是都是彼此的好友。成團問題（clique problem）是一個NP問題。

P則代表了可以有效找到解的問題。我們不知道這300個目標人群的問題是否也是具有P的可解性質。

實際上，令人驚訝的是，成團問題具有“NP完全”的性質。也就是說，當且僅當P=NP時，我們才可以快速有效地解決成團問題。

許多其他問題都具有NP完全的性質，比如3 Coloring問題（是否可以僅使用三種顏色對地圖進行染色，然后讓相鄰的兩個地塊沒有相同的顏色）、旅行商問題（通過城市列表找到最短路徑，讓這個旅行者能夠在路徑所有城市之后回到出發城市），等等。

形式上來說，P代表“確定性多項式時間”，也就是可以在輸入長度的多項式限定時間之內解決的一類問題。NP則代表“非確定性多項式時間”。在實際的算法開發中，我們最好可以換個角度看待P和NP的問題：我們可以將前者視為可有效計算，而將后者視為可有效檢查的問題。

大家如果想更多的了解P和NP的問題，可以去看看2009年的綜述論文，或者一些其他的科普書籍自行了解。也有一些比較偏正式的介紹工作，比如Michael Garey 和 David Johnson在1979年出版的書籍，他們的這本書對于想了解NP完全問題的讀者來說一定不能錯過：

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

2

為什么要討論P和NP問題

在1971年的那個星期二的下午，Cook在ACM計算理論研討會上發表他那篇關于NP完全的論文時，他證明了可滿足性是NP完全的，而重言式是NP難的。論文中也推斷說Tautology是不具備P特性的一個問題，當然，當時沒有對這個問題進行很好的證明。但無論如何，這篇論文以及其中的證明方法，標志著復雜性理論的重大突破。

想要去證明一個數學概念通常具有很大挑戰。算法和證明的基礎概念至少可以追溯到古希臘時期，當然，他們從來沒考慮過NP和P這樣的問題。高效計算和非確定性的理論基礎是在1960年代才發展起來的。但P和NP的問題在這之前很久就已經被提出來了，只是我們沒有給它們正式冠名而已。

庫爾特·哥德爾在1956年曾經寫過一封給馮·諾依曼的信。在信中他就初步描述了P和NP問題。這封信直到1988年才被發現，并廣為流傳。

Richard Karp真正意義上首次將P和NP問題引入大家視野。他在1972年的論文中介紹了該問題，并隨后得到廣泛的關注。

我們知道很多有名的組合問題都是NP完全的，包括Clique, 3-coloring和旅行商問題。1973年，當時在俄羅斯的Leonid Levin在他兩年前獨立研究結果的基礎上發表了一篇新的論文，并在這篇論文中定義了P和NP問題。當Levin的論文傳播到西方的時候，P和NP問題也已經確立了作為計算領域最重要問題的地位。

3

Optiland

Russell Impagliazzo在1995年的一篇經典的論文中描述了P和NP問題具有不同程度可能性的5個層級：

1. 算法：P=NP或理論上等效，例如NP的快速概率算法(fast Probilistic algorithm)
2. 啟發式：NP問題在最壞的情況下很難求解，但平均來說還是可以得到求解的
3. Pessiland：我們可以輕松的創建困難的NP問題，這是所有可能中最糟糕的，因為我們既不能在平均意義上解決難題，也不能從這些問題的難度中獲取任何明顯的優勢
4. Minicrypt：存在加密的單向函數的問題，但我們沒有公鑰加密
5. Cryptomania：公鑰密碼學，也就是說，兩方可以通過公開渠道來交換加密信息，然后通過公鑰解密

上述的5個層級沒有正式的定義，都是通過人們對P和NP問題的了解人為規定的。但是人們普遍認為，Cryptomania這個等級的可能性最高。

Impagliazzo借鑒了P和NP理論中的核心思想——“我們無法擁有一切”。

我們或許可以解決困難的NP問題，或者解決密碼學的重要關鍵，但是不能將兩者同時攻克。

不過，也許我們正在走向事實上的Optiland——機器學習和軟硬件優化等方面的長足進步讓我們能夠在一定程度上解決當年無法設想的問題，包括語音識別、蛋白質折疊解析等。但是大多數情況下，我們的密碼協議仍然是安全的，所以不用太擔心。

在2009年的綜述中，我曾經在其中“如果P=NP怎么辦”的章節中提出，通過使用奧卡姆剃刀法則，學習將會變得容易——我們只需要找到與數據一致的最小程序，也就是問題的關鍵核心。那么此時，原本十分難以解決的視覺識別、語音識別、翻譯以及其他的任務都會變得微不足道。我們還將對天氣、地震和其他自然現象做出更好的預測和理解，以及建模。

今天，我們可以使用人臉識別解鎖手機，可以和一些智能設備語音對話來提出問題并且得到理想的回答，可以將我們說的話、輸入的文字翻譯成另外的語言。我們的手機會收到關于天氣和其他突發事件的警報，它的預測效果比我們之前十幾年前能做到的效果好的多。與此同時，除了對小密鑰長度進行類似暴力破解的攻擊之外，我們的密碼學基本上還是很魯棒和安全的。那么現在，讓我們看看計算、優化和學習方面的最近進展如何將我們帶到Optiland中吧！

4

解決困難問題

2016年，Bill Cook和他的同事決定挑戰一個問題，就是如何以最短的距離訪問英國的每一家酒吧。他們列出了已知的24727家酒吧，并且邁開腿，真的去走遍這些酒吧。這是一次跨越45495239米，大概28269英里的步行之旅，比繞地球一圈還要長。

其實Cook做了個弊，他沒有真的走去每一家酒吧，他忽略了其中一些酒吧來讓這次步行沒那么夸張。這個事情在英國的媒體中宣傳了之后，很多人在底下留言說：你沒有來我家旁邊的這個酒吧呀。于是，Cook和他的公司重新開始計劃，將酒吧的名單增加到49687個，整體的旅行長度就達到了驚人的63739687米，也就是39606英里。但其實，相對于之前的那個旅行，這趟新的尋酒之旅其實只需要多走40%的距離就能達到兩倍多數量的酒吧。

遍歷英國49687家酒吧的全覽圖

這種酒吧遍歷之旅在某種程度上就是旅行商問題的變種，也就是最著名的NP完全問題之一。通過所有49687家酒吧的可能游覽次數約等于3加上后面211761個零這個量級。當然了，Cook的計算機不會搜索整個集合，而是使用了多種優化的技術。更令人印象深刻的是，這次旅行帶有基于線性程序對偶性的最優性證明。

除了旅行商問題之外，我們還看到了求解可滿足性和混合整數規劃方面的重大進步，也就是線性規劃的一種變體，其中一些變量的解要求是整數。當我們使用高精度的啟發式算法，使用快速的處理器、專用的硬件系統和分布式的云計算進行輔助的時候，人們通常可以解決實際中出現的具有好幾萬個變量和幾十上百萬個約束的問題。

面對NP問題時，人們通?？梢詫P問題表述為可滿足性或混合整數規劃問題，并將其扔給目前最好的求解器來借助計算機的力量，自動找到答案。這些工具已經成功用于電路和代碼的驗證、自動化測試、計算生物學、系統安全、產品和包裝設計、金融交易，甚至是一些困難的數學問題求解之中了。

5

數據科學和機器學習

人們通常無法忽視機器學習在近些年帶來的革命性影響，尤其是神經網絡。人工神經網絡建模的概念基礎，基本上是計算加權閾值函數。這種思想起源于1940年代Warren Mcculloch和Walter Pitts的工作。在1990年代，Yoshua Bengio、Geoffrey Hinton和Yann Lecun開發了反向傳播算法，來將深度神經網絡的層數加深，并得到非凡的結果。

與此同時計算機硬件計算、存儲等方面出現突破，那些更快、更加分布式的計算單元，那些專用的硬件和海量的數據有助于推動機器學習完成很多類似人類的功能。ACM認識到Bengio 、Hinton和LeCun的貢獻，并在2018年為他們頒發了圖靈獎。

有的同學可能會問，機器學習怎么和P、NP問題相聯系呢？奧卡姆剃刀說：如無必要，勿增實體。如果P=NP，我們可以用這個思想來創造強大的學習算法：找到與數據一致的最小電路。即便P≠NP，機器學習也可以學習并且近似這種思想，這就賦予它強大的能力。

盡管如此，神經網絡也可能不是真正的“最小”的電路，當然或許可能是盡量小的。今天我們所使用的深度學習方法通常是結構固定的，能夠變動的都是神經元連接上的權重。為了能夠實現足夠泛化的表達能力，這些網絡通常有幾百上千的權重數量。這就限制了深度網絡的能力（也就是不夠簡單）。它們可以在人臉識別上做的很好，但是無法根據示例學習乘法。

通用分布和GPT-3

讓我們考慮二進制字符串的無限集上的分布場景。我們雖然不能擁有均勻分布，但是可以創建一種每個長度相同的字符串都有相同概率的分布。但是，有些字符比其他字符更重要。比如π的前一百萬位數字比隨機生成的一百萬位數字更有意義。

我們可能希望將更高的概率放在更有意義的字符上?，F在我們有很多方法能夠做到這點。實際上，已經有人發現了一種接近任何其他可計算分布的通用分布，這種分布與學習有很大的聯系——例如，任何能夠以小錯誤率學習這個分布的算法，將可以學習所有的可計算分布。

但是問題在于，即使P=NP，這種分布通常也是不可計算的。如果P=NP，我們仍然可以通過創建一個對其他有效可計算分布通用的分布來獲取一些有用的信息。

那么我們能夠從機器學習中得到什么？讓我們考慮生成式預訓練Transformer（GPT）。

在2020年5月GPT-3發布了，它有1750億個參數，并且訓練了4100億個token。這些Token來自很多的文字語料庫。它能夠回答問題，能夠根據提示寫出文字，甚至可以進行一些基礎的編碼工作。盡管還有很長的路要走，但是GPT-3因其生成內容的自然性而受到廣泛的贊譽。

在某種意義上，我們可以將GPT-3視作一種特殊的分布方法。我們可以在其中查看算法生成輸出的概率，這是通用分布的一種弱化版本。如果我們將通用分布限制為具有給定前綴，則會提供由該前綴提示的隨機樣本。GPT-3也可以建立在此類提示的基礎上，無需進一步訓練即可處理范圍廣泛的領域知識。隨著這一系列研究的發布，我們將更接近一個可以執行內置學習的通用衡量標準：從給定的上下文中學習一個隨機樣例。

科學和醫學

在科學方面，我們通過進行大規模的模擬來理解。例如在探索核聚變的反應過程中，我們就取得了一些不錯的結果。研究人員可以應用一種形式化的研究方法，為物理系統創建一個假設，然后使用這個假設，并且不斷的使用這個假設進行反應和模擬。如果我們得到的結果和實際不相符，則丟棄模型，并且重新開始。

當我們得到了一個強大的模型之后，我們就可以在物理模擬系統中進行很多實際實驗中代價昂貴的測試了。如果P=NP，我們可以使用奧卡姆剃刀方法來創建假設，即找到與數據一致的最小電路。機器學習技術可以沿著這條技術路徑前進，使假設的創建自動化。當我們給定數據之后，不論是通過模擬還是真正的實驗得到數據，機器學習就可以創建模型來擬合這些數據，達到最佳的匹配。我們可以使用這些模型進行預測，然后就像之前那樣測試這些預測。

雖然這些技術使我們能夠找到可能遺漏的假設和模型，但是也有可能導致誤報。人類通常會趨向于接受有95%置信度的假設（這意味著20個壞假設中只有一個能夠通過檢驗）。機器學習和數據科學工具能夠讓我們生成假設，這些假設都有著脫離實際建模的風險。這就限制了它的工作范圍，比如醫學工作者就不能承擔這些風險，他們的診斷中如果有這些問題，那會遭到很大的麻煩。生物系統也是一種極為復雜的結構。我們知道人類的DNA形成了復雜的編碼，它描述了我們的身體是如何形成的，以及它們執行的功能。但是很可惜，我們目前對其工作原理知之甚少。

在2020年11月30日，谷歌旗下的DeepMind發布了AlphaFold，這是一種基于氨基酸序列預測蛋白質形狀和結構的新算法。AlphaFold的預測幾乎達到了實際實驗構建氨基酸序列的和測量蛋白質形狀相同的準確度。但是關于DeepMind是否真正“解決”了蛋白質折疊的問題，還存在一些爭議，現在評估其影響還為時過早，但是從長遠的角度來看，這可以為我們提供一種新的數字工具來研究蛋白質，來了解它們是如何互相作用，并且了解如何設計DNA來對抗疾病。

超越P和NP問題的思考：國際象棋

NP就像是一個迷宮一樣，在任意大小的棋盤上各種操作。數獨也是NP完全的問題，它需要從一些正方形中給定的數字設置中求解。但是，當我們問到誰從給定的初始設置中獲勝時，我們是不是就沒辦法給出準確的回答了呢？即使我們有P=NP的前提，它也不一定會給我們一個完美的國際象棋的程序來解決問題，這就像需要設計一個程序，它保證能夠讓白棋走的這一步，逼迫黑棋走那一步，然后白棋再按照計劃走這一步，使得黑棋...，最終是白棋獲勝。人們無法單獨在P=NP上完成所有這些白棋和黑棋的交替。像這樣的游戲往往被稱為PSPACE－hard，即很難計算、或使用合理數量的內存，并且在約定的時間之內求解完成的問題。根據規則的精確限制，國際象棋和圍棋甚至可能更難。

這不意味著如果P=NP，你就不能得到一個好的國際象棋程序。事實上，在某種程度上，象棋的程序體積越大，其智能程度越高。我們可以找到一種有效的計算機程序，它可以擊敗所有尺寸稍小的其他程序。同時，即使沒有P=NP，計算機在國際象棋和圍棋方面也變得非常強大了。1997年，IBM的深藍擊敗了當時的國際象棋世界冠軍。

此外，機器學習為電腦游戲帶來了巨大的進步。我們討論一下聲名大噪的AlphaZero，它是2017年DeepMind開發出來的人工智能程序。

AlphaZero使用了一種被稱為蒙特卡洛樹搜索MCTS的技術，這個技術為兩個玩家隨機移動以確定最佳的行動方案。AlphaZero使用深度學習來預測游戲位置的最佳分布，以優化使用MCTS的獲勝機會。雖然AlphaZero不是第一個使用MCTS的工作，但是它沒有任何內置的人工策略或者使用任何已有的游戲數據庫。AlphaZero只學習了游戲的規則。這就讓AlphaZero在國際象棋和圍棋這兩個運動中大放異彩，除了交替移動和固定大小的棋盤之外，這兩個游戲在規則和目的上沒有任何相似之處。DeepMind最近在MuZero上也有新動作。它甚至都沒有得到完整的游戲規則，只得到了對棋盤位置的一些表示，和合法動作列表，以及對哪些位置是輸是贏有了一些了解。也就是說，現在我們已經發展到了一個階段，在這個階段里，純機器學習在國際象棋或者圍棋這樣的高復雜度的問題中都能輕松擊敗大多數的人類或者啟發式算法。人類的先驗知識只會畫蛇添足、礙手礙腳。對于國際象棋和圍棋這樣的游戲，機器學習可以在P=NP無法滿足的情況下取得成功。太不可思議了。

可解釋的人工智能

許多機器學習算法似乎已經能夠達到不錯的效果，但是我們不知道其中的原因。如果我們仔細的去看語音翻譯或者圖像識別的神經網絡內部參數，很難理解它為什么會做出這樣的動作或者處理。有人可能會問了，它有這個能力就好，我們為什么要關心？以下是幾個原因：信任、公平性、安全性、因果關系。

1. 信任：我們如何知道神經網絡是否正常運行了？除了檢查輸入和輸出之外，我們無法對其他中間的變量進行分析和理解。不同的應用程序具有不同的信任級別。如果Netflix推薦了一個很差的電影，那沒什么問題，但是如果自動駕駛汽車推薦了一個讓車撞墻的轉彎操作，那事兒可就大了。
2. 公平性：很多應用程序都是在訓練集上進行學習的，訓練集中的數據可能不是完全公平或者說沒有偏見的。如果不理解程序，那我們可能無法糾正其中的偏差和歧視。種族歧視可是一個嚴重的話題呦。
3. 安全性：如果我們使用機器學習來監控數據安全系統甚至安保系統，那么不可解釋的機器學習模型可能無法讓你知道他存在的漏洞是什么，尤其是當我們的對手具有適應性的時候。如果我們能夠理解代碼和網絡的結構，就可以發現并且修復這些安全漏洞。當然，如果我們的敵人擁有代碼，他們也有可能發現漏洞并針對其組織攻擊。
4. 因果關系：目前來說，我們最多可以檢查機器學習算法是否只與我們想要的輸出類型相關。但是理解代碼能夠幫助我們理解數據中的因果關系，從而造出更好的科學理論和醫學成果。

如果P=NP，我們能得到更好的計算機程序嗎？如果你有一個解決NP完全問題的快速算法，你就可以用它來找到匹配旅行商問題的最短路徑，但是你不會知道為什么這種方法有效。另一方面，我們都希望能夠得到可解釋的算法，因為能夠深入了解其屬性。在研討會中，我們都在研究可解釋的人工智能，比如ACM Fairness Accountability and Trust會議等。

機器學習的局限性

雖然機器學習在過去的幾十年間取得了令人矚目的進展，但是這些系統遠非完美。在大多數的應用中，它們還是會被人類碾壓。我們將繼續通過新的和優化的算法，收集更多的數據并研發更快的硬件來提高機器學習的能力。機器學習似乎確實有不少的局限。正如我們上面看到的，機器學習讓我們無限逼近P=NP，但是永遠無法達到這個程度。比如，機器學習在破解密碼方面的進展很慢，我們稍后對其進行討論。

機器學習似乎也無法學習簡單的算術關系。比如總結大量的數字規律，以及大數相乘。人們可以想象將機器學習和符號數學工具結合起來，一定能得到很好的效果。雖然我們已經在定理的證明應用方面看到了一些進步，但是距離夢想中的功能還比較遙遠。我也正在寫一篇相關的論文。

同樣的，P=NP將使這些任務變得更加容易，或者至少更加易于處理。機器學習在面對和訓練數據分布不同的樣本的時候，表現通常不好。這可能是由于低概率的邊緣情況，例如在訓練數據中沒有很好的包括所有人種的時候，對于一些國家或者種族的人的識別效果比較差。深度神經網絡算法可能有數百萬個參數，因此，它們可能無法達成良好的泛化分布。如果P=NP，那就可以生成最小尺寸的模型，并且能夠做出最好的泛化，但是如果我們無法進行實驗，我們永遠不知道這是不是P=NP問題。

跟機器學習一樣，我們目前還沒有任何的工作能夠接近真正意義上的通用人工智能。這個通用人工智能是指對某個主題的真正理解，或者真正具有意識或者自我意識的人工系統。定義這些術語可能比較棘手，也具有一些爭議。就我個人而言，我目前還沒見過一個正式的通用人工智能的合理定義，我只是抓住了對它概念的知覺的理解并且總結。我懷疑我們永遠不會實現真正意義上的通用人工智能，即使P=NP。

6

密碼學

雖然我們在解決NP問題方面取得了很大的進展，但是很多密碼學的領域仍舊毫無進展。包括單向函數、安全散列和公鑰密碼等多種形式的加密。一種有效的NP算法，其實是能夠破解所有密碼系統的，除了那些信息理論上安全的密碼系統（比如一次性密碼和一些量子物理學的安全系統）。我們已經看到過很多成功的網絡安全攻擊，但是它們通常源于服務器糟糕的設置、很差的隨機數生成器，或者人為的一些錯誤，幾乎都不是由于密碼學本身的問題所導致的。

現在的大多數CPU芯片都內置AEC，因此一旦我們使用公鑰密碼技術來設置私鑰，我們就可以像發送純文本一樣輕松的發送加密數據了。加密為區塊鏈和加密貨幣提供了底層的技術支持，這意味著人們對加密技術的信任十分高，足以將現金和比特幣進行交換。Michael Kearns和Lesilie Valiant在1994年的研究表明，學習最小的電路，甚至學習最小的有界層神經網絡，都可以用來分解質因數和破解公鑰密碼系統。但是到目前為止，機器學習尚未成功用于破解密碼協議。

可能有人會問，我們既然已經在許多其他NP問題上取得了很多的進展，為什么單單是密碼學上失靈了呢？在密碼學中，我們可以選擇問題，專門設計為這個場景單獨設計的方法來加密，從而達到不錯的效果。而其他的NP問題通常使用通用的、通過程序自己形成的方法來執行。這些自動匹配的方法可能不是量體裁衣的，就并不是最合適和最困難的方法。

量子計算是目前我們知道的唯一一個能夠威脅到互聯網公鑰協議安全的存在。Shor的算法可以用于對大數進行質因數分解和其他相關的數論計算。這種擔憂可以通過幾種方法來加以解決。雖然目前來看量子計算取得了一些令人驚嘆的進步，但是它距離能夠破解當今的密碼系統相去甚遠，畢竟還不能夠處理足夠多的糾纏位。有人估計，可能還得需要幾十年甚至幾個世紀才能真正使用Shor算法+量子計算機對目前的公鑰產生威脅。另外，研究人員在開發對量子攻擊具有抵抗力的公鑰密碼系統方面取得了良好的進展。我們將在本文后面的部分詳細介紹量子計算。

因式分解問題，目前來說并不是NP完全的，即使我們沒有大規模的量子計算機，數學上的突破也肯定有可能推導出很高效有用的解決方案。不論我們如何看待量子計算的未來，一些擁有了多種公鑰系統的計算機都可能解決因式分解問題。

7

摩擦力般的復雜性

話說回來，面對這么多難以計算的問題，我們能有什么優勢呢？或者說我們能從中學習到些什么呢？我想到了密碼學。但是，既然造物主讓某些計算問題變得十分困難和復雜，甚至難以求解和實現，肯定是有內在原因的，這和很多自然界中的摩擦力現象（Friction）十分類似。在物理世界中，摩擦力通常是需要我們額外付出能量做功來克服的，但是如果沒有摩擦力這種常在的阻力，我們甚至無法行走、跑步和前進。同樣的，在計算機的世界里，復雜性雖然會導致一些計算困難，但是如果沒有它，我們可能就會遇到類似于無法前進般的更棘手的問題。在許多情況下，P=NP將消除這種摩擦力。

最近發表的很多計算理論相關論文告訴我們，如果消除了摩擦力般的計算復雜性，那么會產生許多負面的影響。例如，如果消除了計算復雜性，那么人們將不能夠表露自己的思想，人們也只能夠看到其他人所采取的行動，而不知其動作背后的目的。經濟學家有一個術語：偏好啟示（Preference Revelation），這個現象試圖根據我們所采取的行為來推斷其背后的真實目的。在過去的大量時間里，我們通常沒有大量的訓練數據來支持類似模型的訓練，因此這種程序也成為了一種空中樓閣般高度不精確的“藝術品”，無法實用。

時至今日，我們從人們的網絡搜索記錄、他們的社交賬號的照片視頻、游戲賬號的購買記錄，以及在網上的瀏覽記錄、現實生活中的足跡信息，以及各種智能設備中殘留的隱私信息中收取大量的個人信息數據。因此數據集已經很充足。同時，機器學習也可以擁有處理這些復雜信息的能力，因此就可以據此做出非常精確的預測和估計。計算機對我們的了解往往比我們自己對自己的了解還要多。

我們現在的技術已經足夠強大，強大到甚至能夠開發出一個智能眼鏡，讓你戴上它就立刻知道眼前人的各種信息，姓名、年齡、身高體重、興趣愛好，甚至是政治偏好。也就是說，在大數據的時代，由于機器學習和大量隱私信息的存在，本來十分復雜、幾乎不可能實現的一些問題被計算機攻克，也就帶來了隱私的泄露——復雜性不再能為我們提供隱私的保護。我們需要通過法律和對企業的責任約束來保護個人的隱私安全。

計算機世界的“摩擦”現象可以超越隱私。美國政府在1978年取消了對航空公司定價的管制，因此如果旅客想要找到一條最便宜的航線，就需要打好多個電話給很多家航空公司，或者通過旅行社來尋找。但是旅行社嘛，通常不會盡心盡力的幫你尋找最便宜的，而是尋找對他們利益最高的那條路線。各個航空公司的生存理念不同，有的可能致力于保持高水平的服務質量，因此價格稍貴；有些則是想要用低價來吸引更多的乘客。今天，我們可以很容易的通過計算機程序找到最便宜的航空公司的航線信息，因此航空公司也都跑去在價格上苦苦鏖戰競爭，并期望計算出最佳的定價來提高上座率，此時服務態度和體驗可能就被犧牲掉了。

計算機的“摩擦力”或者說復雜性，也有助于打擊作弊問題。我在1980年讀大學的時候，天天被微積分問題虐，整天都在各種數學計算，生不如死。但是時至今日，這些微積分問題在Mathematica和Matlab面前都是弟弟，一行指令輕松破解。我現在當老師了，在我的課程上，我甚至留不出一些網上無法搜索到的家庭作業題目來讓學生訓練。更可笑的時候，我甚至可以使用GPT-3或者它的后續優化代碼來生成一些家庭作業。那么當GPT之類的工具已經可以自動回答這些很復雜的問題的時候，我們如何激勵學生，或者說防止他們作弊偷懶呢？

股票交易也是一個重災區。在過去，股票交易通常需要在一個很大的交易所中進行，就像我們在電影中看到的那樣，交易員在那里用一個很帥的手勢來指揮買入和拋售，用一個眼神來匹配最佳的價格。但是現在，算法會自動適應最佳的價格并且買入拋售股票。雖然偶爾會導致“閃崩”的現象。機器學習算法已經很強大了，他們能夠替代人類進行一些決策，也能進行人臉識別，將社交媒體的內容和用戶進行匹配，也能進行一些司法判決。這些決策系統都為人們提供了便利，但也帶來了很大的社會挑戰。比如歧視問題和政治兩極化的問題正在被拉大。這個問題很復雜我們無法一言概之。

上述的問題只是此類場景中的一小部分。作為計算機科學家，我們的目的是使計算盡可能高效和簡單，但我們必須保留減少計算復雜性，也就是計算“摩擦力”的成本。

8

量子計算機的力量

隨著摩爾定律的失效，計算機研究人員將目光轉移到量子計算機的領域，這些年，量子計算機的研究和應用正在經歷大幅的增長。谷歌、微軟和IBM等大型科技公司，以及各種創業公司都在量子計算機方面投入大量資源進行研究。美國發起了國家級的量子計算研究計劃，中國等其他國家也在紛紛效仿。

在2019年，谷歌宣布他們已經通過使用53個量子比特的量子計算機實現了“量子霸權”，解決了當前傳統計算機無法解決的很多計算任務。雖然有很多人質疑這個說法，但是我們無疑的正在處于量子計算新時代的起點之上。盡管如此，我們距離能夠跑起來Peter Shor的量子算法，以及擁有一臺真正的量子計算機，還有相當遠的距離。保守來說，我們還需要幾萬個量子位的距離需要攻克。通常來說，量子計算機可以被理解成是由比特表示的狀態數的系統，比如53個量子比特計算機的2^53個狀態。這可能說明，我們可以通過創建特別多的狀態位，也就是使用量子計算來解決NP完全問題——也就是大力出奇跡。但不幸的是，目前我們無法證明量子計算機能夠充分操控這些狀態位，也就是不知道使用什么算法來解決NP完全問題，在這個角度上，這個問題已經超出了Grover的算法限制。

9

復雜性更新

自從2009年以來，我們在高效計算理論方面取得了一些重大的進展。雖然這些結果在解決P和NP方面沒什么幫助，但是它們可能從一旁幫助理解相關的問題，并且啟發后世的一些研究發展。

圖同構

一些NP問題無法表征為P（有效可解）或NP完全問題（與Clique問題一樣難的問題）。我們之前討論過的最著名的整數因式分解仍然需要指數級的時間來求解。對于另一個這樣的問題，也就是圖同構問題，我們最近看到了一些戲劇性的進展。圖同構問題是指，人們可否找到兩個圖在統一表示下完全相同。具體舉例來說，就像在Facebook中，當我們給定了兩組1000人，我們能否將他們映射到另一個組中，在那個新組中好友的關系不變。（小A和小B是好友，在另一群人中A’和B’也是好友）

這個圖同構的問題在80年代中有了一些理論上的證明。在80年代，有人用交互式的方法證明了圖同構問題不是NP完全的，而且它其實不是很困難，在一些實際的情況下，使用啟發式的方法也能快速找到解決答案。盡管如此，我們仍然無法找到一個能夠在所有場景中都快速找到解的算法。Laszlo Babai在2016年對該問題進行了深入研究，并發表了一種用于圖同構的多項式時間的解決算法。簡單來說，P中的問題在多項式時間內如果可以得到解決，也就是對于某個常數k，復雜度是n^k，其中n是輸入的大小，比如每組的人數。擬多項式時間算法在時間n^(logn)k內執行，只比多項式時間差一點點，但起碼比我們預計的NP完全問題所需要的2^n^ε的復雜性好的多。

Babai的證明結合了組合學和群論，是一個非常棒的工作。雖然距離讓這個算法能夠在多項式時間內執行完還有些遠，但是Babai提供了一個重要的理論結果。這在P和NP完全問題之間取得了一項重大的進展。

電路設計

如果NP在完整的電路設計的基礎上（也就是與或非門）沒有最小的電路，那么就不存在P=NP的解。雖然在1980年代的電路發展黃金年代中，沒有明確的證明否定P=NP的假設。在2009年的各項調查中，也說明在過去20年中，電路復雜性也沒有取得重大的成果。在1987年，Razborov和Smolensky證明說不可能用與或非和Mod_p門的恒定深度電路計算某些固定素數p的多數函數。但是對于帶有Mod_6門的電路來說，我們幾乎無法證明這個結果。即便是我們可以證明NEXP（NP的指數時間版本）無法通過與或非和Mod_6門的小型、恒定深度的電路進行計算，P和NP是否相等的問題在幾十年見也仍舊無法得到解答。話說回來，恒定深度的電路在理論上被認為是具有很弱的可計算性的，我們在這些年一直沒有取得實質性的進展，在電路的算法最新產出上的無人問津也側面證明了這個現象。

在2010年，Rayan Williams表明NEXP確實不具有那些使用Mod_6或其他Mod門一樣的恒定深度的電路。因此，他創造了一種新的技術，使用可滿足性算法進行解決。這種算法的實現下界比嘗試所有可能，或者使用一些復雜性工具來暴力實現來說要好一些。后來，Williams和他的學生Cody Murray進行了進一步的研究，結果表明，可以在任何固定的沒有帶Mod_m門的小的恒定深度的電路中，都有非確定性擬多項式時間的解。然而，證明NP沒有任意深度的小回路這個問題，仿佛仍然遙不可及。

復雜性的反擊？

在2009年的那篇綜述中，我在名為“新希望”的章節中討論了一種新的幾何復雜性理論方法，這個方法基于Ketan Mulmuley和Milind Sohoni開發的代數幾何和表示論來攻克P和NP問題。簡而言之，Mulmuley和Sohoni創建了高維的多邊形空間，以在NP的代數版本中找到P和NP的映射，從而在這個空間中重構、理解并解決該問題。他們的一個猜想中，假設多邊形包含某個表示理論對象的特殊屬性。在2016年，Peter Burgisser、Christian Ikenmeyer和Greta Panova從理論上證明了這種方法是不可能滴。

雖然Burgisser和Ikenmeyer、Panova的研究成果否定了GCT分離P和NP的方法，但是并沒有將這種實驗方法和思路進行否定。人們仍然可以根據這種表示理論對象的數量創建不同的多邊形空間。盡管如此，我們還是無法孤注一擲的認為多邊形方法能夠在不久的將來解決P和NP的問題。

10

不可能的可能性

當我們反思P和NP問題時，我們看到這個問題有很多不同的含義。P和NP的數學正式定義仍然是它的官方定義，雖然很冷冰冰但是含義最為完全。而且能夠解決這個數學問題的人還能給你的到數百萬美元的賞金不是嗎。

有時候，我們雖然可以通過可計算理論、電路、證明和代數幾何等工具看到解決P和NP的方法，但是目前沒有能夠完全解決P和NP問題的有力方法。從這個角度上來說，我們正在抽象P和NP問題到一些領域中，降低了它的難度，也就是距離原問題越來越遠。

在現實生活中，我們也有很多秉待解決的實際NP問題。在1976年出版的經典著作《計算機與難處理性：NP完全性理論指南》一書中，Garey和Johnson舉了一個倒霉的員工的例子，他老板讓他去解決一個NP完全優化的問題。最終的時候，這個員工苦惱地找到老板說，我實在沒轍了，找不到一個有效的算法來解決這個問題，而且不光是我，這個世界上不管是比爾蓋茨還是沃茲尼亞克都束手無策。書中說，這個老板不應該解雇這名員工，因為沒有其他的人能夠解決這個問題。

在P和NP的早期，我們將NP完全性視作障礙。這些是我們無法解決的問題。但是隨著計算機的發展和進步，我們發現可以通過啟發式與暴力計算的組合，在很多NP問題上取得很好的進展。在Garey和Johnson的故事中，如果我是老板，我可能不會解雇那名倒霉的員工，而是建議他使用一些新的方法，比如混合整數編碼、機器學習以及暴力搜索的方法進行破解。NP完全意味著不可能，這個想法其實已經out了，它的時代也已經成為過去式了。NP完全，只是意味著可能沒有始終有效和可擴展的算法而已，但是問題，還是有可能被解決的。

在我2013年發表的P和NP的書中，我有一章名為“美麗新世界”的文字。我在其中提到了一個理想化的世界，在那里，捷克數學家證明了P=NP，從而為所有NP問題提供了一種非常有效的解決算法。雖然我們不會也可能永遠不會生活在這樣的理想世界中，但是隨著醫學的進步，隨著虛擬世界、元宇宙等新概念的崛起，P=NP這個古老的美妙話題似乎也不再遙不可及。

但是，話說回來，我們正在朝著幾乎能夠顛覆P=NP問題思想的方向大步前進。與其一直將其視為算法的障礙，不如去想象P和NP的解決之道，在其中探索一些新的方向，發掘出其中不可能的可能性。

原文鏈接：https://cacm.acm.org/magazines/2022/1/257448-fifty-years-of-p-vs-np-and-the-possibility-of-the-impossible/fulltext

---

雷峰網(公眾號：雷峰網)雷峰網