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

作者 | Lance Fortnow

編譯 | Don

編輯 | 青暮

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

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

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

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

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

1

P和NP問題

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

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

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

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

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

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

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

形式上來說，P代表“確定性多項式時間”，也就是可以在輸入長度的多項式限定時間之內(nèi)解決的一類問題。NP則代表“非確定性多項式時間”。在實際的算法開發(fā)中，我們最好可以換個角度看待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計算理論研討會上發(fā)表他那篇關(guān)于NP完全的論文時，他證明了可滿足性是NP完全的，而重言式是NP難的。論文中也推斷說Tautology是不具備P特性的一個問題，當(dāng)然，當(dāng)時沒有對這個問題進(jìn)行很好的證明。但無論如何，這篇論文以及其中的證明方法，標(biāo)志著復(fù)雜性理論的重大突破。

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

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

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

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

3

Optiland

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

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

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

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

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

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

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

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

4

解決困難問題

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

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

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

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

除了旅行商問題之外，我們還看到了求解可滿足性和混合整數(shù)規(guī)劃方面的重大進(jìn)步，也就是線性規(guī)劃的一種變體，其中一些變量的解要求是整數(shù)。當(dāng)我們使用高精度的啟發(fā)式算法，使用快速的處理器、專用的硬件系統(tǒng)和分布式的云計算進(jìn)行輔助的時候，人們通?？梢越鉀Q實際中出現(xiàn)的具有好幾萬個變量和幾十上百萬個約束的問題。

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

5

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

人們通常無法忽視機(jī)器學(xué)習(xí)在近些年帶來的革命性影響，尤其是神經(jīng)網(wǎng)絡(luò)。人工神經(jīng)網(wǎng)絡(luò)建模的概念基礎(chǔ)，基本上是計算加權(quán)閾值函數(shù)。這種思想起源于1940年代Warren Mcculloch和Walter Pitts的工作。在1990年代，Yoshua Bengio、Geoffrey Hinton和Yann Lecun開發(fā)了反向傳播算法，來將深度神經(jīng)網(wǎng)絡(luò)的層數(shù)加深，并得到非凡的結(jié)果。

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

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

盡管如此，神經(jīng)網(wǎng)絡(luò)也可能不是真正的“最小”的電路，當(dāng)然或許可能是盡量小的。今天我們所使用的深度學(xué)習(xí)方法通常是結(jié)構(gòu)固定的，能夠變動的都是神經(jīng)元連接上的權(quán)重。為了能夠?qū)崿F(xiàn)足夠泛化的表達(dá)能力，這些網(wǎng)絡(luò)通常有幾百上千的權(quán)重數(shù)量。這就限制了深度網(wǎng)絡(luò)的能力（也就是不夠簡單）。它們可以在人臉識別上做的很好，但是無法根據(jù)示例學(xué)習(xí)乘法。

通用分布和GPT-3

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

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

但是問題在于，即使P=NP，這種分布通常也是不可計算的。如果P=NP，我們?nèi)匀豢梢酝ㄟ^創(chuàng)建一個對其他有效可計算分布通用的分布來獲取一些有用的信息。

那么我們能夠從機(jī)器學(xué)習(xí)中得到什么？讓我們考慮生成式預(yù)訓(xùn)練Transformer（GPT）。

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

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

科學(xué)和醫(yī)學(xué)

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

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

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

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

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

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

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

此外，機(jī)器學(xué)習(xí)為電腦游戲帶來了巨大的進(jìn)步。我們討論一下聲名大噪的AlphaZero，它是2017年DeepMind開發(fā)出來的人工智能程序。

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

可解釋的人工智能

許多機(jī)器學(xué)習(xí)算法似乎已經(jīng)能夠達(dá)到不錯的效果，但是我們不知道其中的原因。如果我們仔細(xì)的去看語音翻譯或者圖像識別的神經(jīng)網(wǎng)絡(luò)內(nèi)部參數(shù)，很難理解它為什么會做出這樣的動作或者處理。有人可能會問了，它有這個能力就好，我們?yōu)槭裁匆P(guān)心？以下是幾個原因：信任、公平性、安全性、因果關(guān)系。

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

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

機(jī)器學(xué)習(xí)的局限性

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

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

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

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

6

密碼學(xué)

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

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

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

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

因式分解問題，目前來說并不是NP完全的，即使我們沒有大規(guī)模的量子計算機(jī)，數(shù)學(xué)上的突破也肯定有可能推導(dǎo)出很高效有用的解決方案。不論我們?nèi)绾慰创孔佑嬎愕奈磥?，一些擁有了多種公鑰系統(tǒng)的計算機(jī)都可能解決因式分解問題。

7

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

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

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

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

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

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

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

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

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

8

量子計算機(jī)的力量

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

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

9

復(fù)雜性更新

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

圖同構(gòu)

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

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

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

電路設(shè)計

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

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

復(fù)雜性的反擊？

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

雖然Burgisser和Ikenmeyer、Panova的研究成果否定了GCT分離P和NP的方法，但是并沒有將這種實驗方法和思路進(jìn)行否定。人們?nèi)匀豢梢愿鶕?jù)這種表示理論對象的數(shù)量創(chuàng)建不同的多邊形空間。盡管如此，我們還是無法孤注一擲的認(rèn)為多邊形方法能夠在不久的將來解決P和NP的問題。

10

不可能的可能性

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

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

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

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

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

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

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

---

雷峰網(wǎng)雷峰網(wǎng)(公眾號：雷峰網(wǎng))

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。