最新證明面臨質疑：P/NP問題為什麼這麼難？
編譯 | 張林峰（普林斯頓大學應用數學專業博士研究生）
責編 | 陳曉雪
●
●
●
P和NP是否相等通常被認為是理論計算機科學中最重要的難題，也是克雷數學研究所高額懸賞的七個千禧年難題之一。
5天前，德國波恩大學的計算機科學家Nobert Blum在arXiv上傳了一份38頁長的論文，聲稱證明了P/=NP
（P不等於NP）
，引發學界的關注與討論(https://arxiv.org/abs/1708.03486)
。
?
Nobert Blum宣稱證明P/=NP的論文很快，加州大學伯克利分校的電子工程與計算機科學教授Luca Trevisan就在社交平台上發表意見稱，安德烈耶夫方程
(Andreev』s function)
，也即論文證明中的關鍵，在文中被認為具有超多項式電路複雜度(superpolynomial circuit complexity)
，而實際上可以被高斯消去法(Gaussian elimination)
解決，所以僅有多項式複雜度，這使得文中的證明不能成立。該證明是否正確還有待人們的進一步仔細檢查。
?
Luca Trevisan認為，Blum文中的證明不能成立近年來，不乏有人聲稱證明了P等於或者不等於NP，但都被發現證明過程有誤。事實上，到目前為止，還沒有人能夠回答這個問題。2002年，有70位數學家和計算機科學家被邀請參與一次投票，投P是否等於NP。其中的61位認為P不等於NP，而剩下的人里有好幾個都表示投「等於」只是為了採取相反的立場。
粗略地說，P代表一組相對容易的問題，而NP代表一組看起來非常難的問題。因此，P= NP將意味著明顯困難的問題其實有比較容易的解決方案——當然，其中的細節還要麻煩一些。
實際上，量子計算機、圖同構問題等人們熱衷的最新進展無不指向P對NP問題。那麼，P與NP問題究竟是什麼？它的解決將意味著什麼？它難在哪裡？量子力學為它帶來了什麼？又有什麼理論、將在何時有可能解決它？本文試圖對這些問題提供簡單的介紹和探討。
1
當我們說P/NP問題時，說的是什麼？
圖靈時期的計算機科學關注的主要是問題的可計算性
（computability）
，也即一個問題是否可以被計算機描述並解決。之後，隨著可計算性問題的澄清，計算機科學家逐漸將注意力轉移到了另一個問題，即問題的複雜性（complexity）
：執行一個給定的演算法需要多長時間？不過，計算機科學家的答案不是幾分鐘或者幾毫秒，而是所需時間與問題規模的函數關係。《麻省理工學院新聞
》(MIT News）
曾發表過一篇解釋P/NP的文章。這篇文章指出，想像有一張未經排序的數字列表，然後寫一個尋找最大值的演算法。首先顯然，該演算法必須要查詢列表中的所有數字。但是，如果它只是在每一步查詢一個數字，然後只更新並記錄當下的最大數，那麼對於每個數字，它只需要查詢一次。於是，該演算法的執行時間與它處理的問題規模，即計算機科學家們所指的N，直接成正比。當然，大多數演算法是更為複雜的，因此比尋找最大值演算法的效率要低。但是有許多常見演算法的執行時間與N^2，或者N log(N)成正比。
?
無序數字列表求最大值的演算法示意。MAX指最大值，N指數字個數，a[i]指當前查詢的第i個數字一個只包含常數、N、N^2以及N的其他次方的數學表達式稱為一個多項式
（polynomial）
，這就是「P = NP」中的「P」所代表的單詞。一般來說，P代表求解時間與N的多項式成正比的問題的集合。類似地，PSPACE代表所用空間與N的多項式成正比的問題的集合。
顯然，一個執行時間與N^3成正比的演算法的要比與N成正比的演算法慢
（對於足夠大的N）
，但這種差異與多項式和指數的差異比起來要渺小得多。《麻省理工學院新聞》的這篇文章指出，如果一個執行時間與N成正比的演算法用1秒可以解決包含100個輸入元素的問題，那麼與N^3成正比的演算法大概需要3個小時。但是，一個執行時間與2^N成正比的演算法需要300艾（1艾等於10的18次方）
年的時間來解決同樣的問題。所以2^N與N的多項式的差異要比N^3和N之間的差異多的多。NP（
Nondeterministic Polynomial time，非確定型多項式時間）
指的是其解可以在多項式時間內被驗證的問題集合。容易想像的是，許多NP問題看起來需要指數時間來解決。例如，對於大整數質因子分解這個或許是NP中最著名的問題，驗證一個解幾乎只需要做一次乘法，但要真去解的話似乎需要系統地嘗試大量的可能解。所以「P是否等於NP」的意思是說「如果一個問題的解可以在多項式時間內被驗證，那麼是否可以在多項式時間內找到這個解」。這個問題的部分魅力在於，大量典型的看起來需要指數時間去解決的NP問題被稱為「NP完全問題」
（NP-complete，NPC）
，它們可以在多項式時間內相互轉化。這意味著如果其中一個問題是多項式時間可解的，那麼所有其他問題也都是。第一個NPC問題是庫克-列文
(Stephen Cook， Leonid Levin)
給出的布爾可滿足性問題（Boolean Satisfiability problem，SAT）
。於是，任何NP問題都可以在多項式時間內轉化為SAT問題。與此等價地，如果SAT在P中，那麼P=NP。這便是著名的庫克-列文定理（Cook–Levin theorem）
。在現實生活中，NP完全問題是相當普遍的，特別是在大的調度任務中。《麻省理工學院新聞》曾列舉了一個著名的NP完全問題是所謂的旅行商問題（
Traveling Salesman Problem，TSP）
。該問題在當今很發達的物流業中可以表述為：一個物流配送公司欲將N個客戶的訂貨沿最短路線全部送到，那麼它應該如何確定最短路線？對於這一問題，P=NP意味著這樣的物流分配可以很快地進行，但反之則意味著當物流規模逐漸擴大時，我們將無法在有效時間內找到最短路線。綜上，我們將P、NP、NPC以及PSPACE等複雜度類及它們之間相互的關係總結如下圖。我們還知道，SAT與TSP在NPC中，而圖同構和大整數分解等問題既沒有被證明在P中，也沒能被證明在NPC中，大部分理論計算機科學家認為它們的難度介於P與NPC之間
（NP-intermediate,NPI）
。
?
複雜度類關係示意圖。實線框表示已被證明的真包含關係，虛線框表示尚未被證明的真包含關係（下同）2
P/NP問題有什麼用，又難在哪裡？
幾乎沒有一個數學家、物理學家或者計算機科學家相信P真的等於NP——那樣的話，所有的密碼將很容易被破解，很多困擾人們的數學問題將有辦法被解決，人工智慧將突破連連……一個想到答案和驗證答案所需時間相當的世界，會是我們所生存的世界嗎？如果是的話，為什麼世界上最聰明的數學家會對著一些數學問題思索良久，而當他們想出答案時，又是那麼快地就能驗證答案是否正確呢？既然大多數人覺得P不等於NP，那麼它的證明究竟有什麼用？研究它又有什麼意義？
麻省理工學院
（MIT）
數學系主任以及計算機科學、人工智慧實驗室計算理論小組（Theory of Computation Group，TOC）
成員Michael Sipser認為，P/NP問題有助於我們更加深入地理解計算複雜性。「一個主要的應用是在密碼學領域，其中密碼安全性經常是由計算任務的複雜性保障的，」Sipser說，「互聯網安全交易常用的RSA加密方案就是研究特定數論計算複雜性問題時的一個副產品」。此外，「P/NP問題已經被數學界的人們廣泛認為是基本、重要而美麗的數學問題。我認為它是數學和計算機科學之間的橋樑。」
?
Michael Sipser對於同樣的問題，TOC的另一位成員、MIT計算機科學和人工智慧實驗室副教授Scott Aaronson
（現為德克薩斯大學奧斯汀分校計算機科學教授）
也提供了他的回答：「是的，幾乎所有的人都相信P是不等於NP的。但是，研究這個問題的過程要比結果重要。這個過程中，為了證明它，我們將需要大量的對計算的嶄新理解。我們想要證明的是什麼？是對於解決所有這些優化問題、搜索問題、找到定理的證明、找到航空公司的最佳路線設計、破解密碼——所有這些不同的東西，無論你多麼聰明，都不能找到有效的演算法。所以，為了證明這樣的命題，一個先決條件就是要了解所有可能的有效演算法組成的空間。這可是一個令人難以置信的艱巨任務。我們期望的是，在證明這件事情的過程中，我們會了解到大量的遠超我們想像的關於有效演算法的理論，而且非常非常有可能發現新的、當下無法預知的在某些地方有神奇應用的演算法。理論計算機科學的歷史經常是這樣的，你用來證明一些東西不可能的論據恰恰可以反過來說明別的東西可能，反之亦然。最簡單的例子是加密，當你證明一些問題難以被有效解決時，你也會得到一個有用的編碼方法。」
?
Scott Aaronson值得一提的是，在研究P/NP問題時，很多複雜性類的引入有著廣泛而深入的理論意義和實際意義，有界錯誤概率多項式時間類
（bounded-error probabilistic polynomial time，BPP）
便是其中之一。此時不得不提的便是概率演算法。一方面，20世紀80年代以來很多科學家認為概率的引入有助於解決P/NP問題。另一方面，如果非要和下文中的量子力學扯上關係，概率演算法是非說不可的——量子演算法天然便是概率演算法！典型的概率演算法包含「擲硬幣」的指令，並且擲硬幣的結果可能影響演算法後面的執行和輸出。BPP是這樣的一類判定問題：如果答案是肯定的，那麼存在?個多項式時間隨機演算法以?於2/3的概率接受，如果答案是否定的則?於1/3。換句話說：給定任何輸?，該演算法錯誤的概率最多為1/3。1/3這個數字的意義僅僅在於它是某個?於1/2的正的常數。任何這樣的常數都是?樣好的。為什麼呢？嗯，假設我們得到?個犯錯概率為1/3的BPP演算法。如果我們真想要的話，我們可以很容易地將這個演算法的犯錯概率修改為最多
（?如說2^{-100}）
。怎麼做呢？我們僅需要反覆運?該演算法?百次，然後輸出占多數的答案！所以，這就是BPP：很多人認為，BPP是經典物理學控制的宇宙中計算機可以切實解決的所有問題組成的類。BPP與P、NP等的關係如何呢？顯然，P包含於BPP，因為P便是不需拋硬幣、輸出結果確定的BPP。而現在很多科學家認為，P可能等於BPP，這是又一個開放性問題。有趣的是，我們甚至還不知道BPP與NP的關係，而只知道BPP包含於PSPACE。因而，下面的關係圖中，虛線又增多了：
?
BPP加入後的複雜度類關係示意圖看起來，BPP的加入未必可以解決P/NP問題，反倒帶來了更多尚未有答案的問題。而事實上，更多的複雜度類因為研究的需要被引入了進來。在Scott Aaronson開的複雜度類動物園
（Complexity Zoo）
中，人們不斷地加入新的複雜度類，到現在已經有了498隻複雜性類！人們不知道這個研究過程何時是個終點。綜上所述，如果P=NP成立，那麼世界將換一個模樣；而如果能夠證明二者不相等，我們也會取得足夠多的新突破。這正是其重要性所在。而它很困難的原因恰恰在於，我們還沒能較為清楚地看到一條通往它的道路。
3
量子力學帶來了什麼？
「你要是光看報、讀雜誌等，你可能會覺得一個量子計算機可以通過『並行地嘗試每一個可能的解』，然後『在心臟跳一下的時間裡解決NP完全問題』。嗯，大概那是門外漢們對於量子計算機最核心的錯誤印象。」Scott Aaronson在接受《麻省理工學院新聞》採訪時說。
「Peter Shor
（另一位TOC成員）
發現大整數分解的多項式量子演算法時，量子計算界確實炸了。」在《麻省理工學院新聞》的報道中，Sipser介紹說。「Peter的突破引發了計算機和物理兩個領域的一大波研究。事實上，Shor的發現一度點燃了人們利用微觀尺度下反直覺的量子力學來在多項式時間內解決NP完全問題的希望。但現在看來這似乎不太可能：大整數分解問題實際上是幾個不知道是否為NP完全的NP困難(NP-hard)
問題。」同樣地，人們不能證明不存在多項式的大整數分解演算法，所以儘管人們相信量子計算對於大整數分解這樣的問題會帶來計算能力的提升，但這點同樣尚未得到證明——更別提對於一般問題的指數級別的突破了。
?
Perter Shor對此，Scott Aaronson介紹了Grover演算法作為例子。Grover演算法對於輸入規模為N的無序資料庫給出的~2^{N/2}時間複雜度的量子搜索演算法。但早在Grover的演算法之前，Bennett等人已經證明~2^{N/2}是最優解了！換句話說，任何在2^N那麼大的大海中撈一根針的量子演算法都需要至少~2^{N/2}步。相應地，經典計算機需要~2^N步。所以至少可以說，對於「一般的」或者「無結構的」搜索問題，量子計算機對於經典計算機來說只能給出某種加速——事實上是平方加速——但不會是像Shor演算法那樣的指數加速。
為什麼這個加速會是平方的，而非立方或者其他什麼的？Scott Aaronson嘗試著給出了答案，且盡量不牽扯到Grover演算法或者Bennett等人最優化證明的具體細節。他認為，從根本上講，我們得到平方加速的原因是，量子力學是基於2-範數而非1-範數的。經典來講，如果有N個解，其中只有一個是正確的，那麼查詢一次後我們距離得到正確答案便有了1/N的概率，查詢兩次後便有了2/N的概率，查詢三次3/N，依此類推。因此，我們需要~N次查詢來獲得足夠大
（即接近1）
的概率猜出正確答案。但是如果用量子力學，我們是對一組幾率幅態矢進行線性變換，它是概率的平方根。所以我們這樣考慮這個問題：查詢一次後我們有1/sqrt{N}的幾率幅得到正確答案，查詢兩次後是2/sqrt{N}幾率幅，查詢三次後是3/sqrt{N}幾率幅，依此類推。所以經過T次查詢後，我們得到正確答案的幾率幅為T/sqrt{N}，然後概率便是|T/sqrt{N}|^2= T^2/N。因此我們需要大約T ~sqrt{N}次查詢來得到接近於一的概率。量子計算機概念的引入給我們帶來了新的複雜度類，其中最典型的一個便是BQP，即有界錯誤量子多項式時間類
（bounded-error quantum polynomial time）
。與BPP類似地，BQP指可以在多項式時間內用量子計算機以小於1/3的錯誤概率解決的問題的集合。很多人認為，BQP是量子物理學控制的宇宙中計算機可以切實解決的所有問題組成的類。BQP包含BPP與P，且包含於PSPACE，但它與NP的關係就沒那麼確定了。於是，新的關係圖如下：
?
BQP加入後的複雜度類關係示意圖綜上所述，量子力學的加入一定程度上為P/NP問題帶來了新的曙光，但是想要解決P/NP問題還是需要走很長的路。
4
可能的解決方案？
在通往P/NP問題的路上，有很多的嘗試，例如量子力學、電路下界、互動式證明技術等，都先是讓人們看到了希望，然後隨著研究的深入，又讓人們覺得這些可能還不夠。那麼，還有什麼「有希望的」解決方案嗎？Scott Aaronson介紹了芝加哥大學計算機系教授Ketan Mulmuley的幾何複雜性理論綱領
（Geometric Complexity Theory program, GCT program）
。GCT試圖將P/NP問題與代數幾何、表示理論等很多看起來比較遠的數學概念聯繫起來。
?
Ketan Mulmuley「我覺得GCT就像計算機科學領域的弦論，」Scott Aaronson說，「一方面，它實現了如此驚人的數學聯繫，以至於一旦你看到它們，你就會覺得這個綱領一定會在正確的道路上。而另一方面，如果你用已經解決了多少它最初想解決的問題，而不是這一綱領本身來評價它的話，那麼可能它連最初的想法都還沒有實現。」也就是說，或許正是因為還沒有足夠深入的了解，所以GCT還保留著解決P/NP的希望。「甚至GCT綱領最瘋狂的支持者也預測說得有幾十年的跋涉，而且其在數學上的複雜性也嚇唬到了其他每個人。」
是的，P/NP問題就是這麼難。
感謝Scott Aaronson對本文的意見。
主要參考文獻：
1. MIT News對於Michael Sipser和Scott Aaronson的採訪，採訪部分獲Scott Aaronson授權翻譯：
http://news.mit.edu/2009/explainer-pnp
http://news.mit.edu/2010/3q-pnp
2. Aaronson S. Quantum computing since Democritus[M]. Cambridge University Press, 2013.
3. Sipser M. Introduction to the Theory of Computation[M]. Cengage Learning, 2012.
製版編輯：斯嘉麗
丨
本頁刊發內容未經書面許可禁止轉載及使用
公眾號、報刊等轉載請聯繫授權
copyright@zhishifenzi.com
歡迎轉發至朋友圈
▼點擊查看相關文章
遺傳資源爭議|天使粒子爭議
|大望遠鏡爭議
施揚
|潘卓華|楊璐菡
|劉若川
|
張鋒
|薛其坤
張毅|王曉東
|張啟發
|崔維成
|
潘建偉|
李佩
盧煜明
|
王小凡|吳文俊
|袁鈞瑛
|
張純如
知識分子
為更好的智趣生活
ID：
The-Intellectual
投稿：
zizaifenxiang@163.com
授權：
copyright@zhishifenzi.com
長按二維碼，關注知識分子
購買課程
請點擊下方「閱讀原文」
▼▼▼
點擊「閱讀原文」，了解課程詳情，立享限時特惠！
※張鋒、杜德納等獲阿爾伯尼獎 | 快訊
※大望遠鏡爭議之四：評審組長Anderson的回復｜林潮的直白評論與陳建生最新回應
※不談復甦，現在能夠完好凍存人體嗎：原理技術都不成熟
※其樂融融——太空的生活如此多姿多彩！
※基因變異實驗揭曉螞蟻如何形成高效群體行為能力
TAG:知識分子 |