|
P和NP是否相等通常被認為是理論計算機科學中最重要的難題，也是克雷數(shù)學研究所高額懸賞的七個千禧年難題之一,。 5天前,，德國波恩大學的計算機科學家Nobert Blum在arXiv上傳了一份38頁長的論文，聲稱證明了P/=NP（P不等于NP）,，引發(fā)學界的關注與討論 (https:///abs/1708.03486),。 ?Nobert Blum宣稱證明P/=NP的論文 很快，加州大學伯克利分校的電子工程與計算機科學教授Luca Trevisan就在社交平臺上發(fā)表意見稱,，安德烈耶夫方程 (Andreev’s function),，也即論文證明中的關鍵，在文中被認為具有超多項式電路復雜度 (superpolynomial circuit complexity),，而實際上可以被高斯消去法 (Gaussian elimination) 解決,，所以僅有多項式復雜度，這使得文中的證明不能成立,。該證明是否正確還有待人們的進一步仔細檢查,。 ?Luca Trevisan認為，Blum文中的證明不能成立 近年來,，不乏有人聲稱證明了P等于或者不等于NP,，但都被發(fā)現(xiàn)證明過程有誤。事實上,，到目前為止,，還沒有人能夠回答這個問題。2002年,，有70位數(shù)學家和計算機科學家被邀請參與一次投票,，投P是否等于NP。其中的61位認為P不等于NP,，而剩下的人里有好幾個都表示投“等于”只是為了采取相反的立場,。 粗略地說，P代表一組相對容易的問題,，而NP代表一組看起來非常難的問題,。因此，P= NP將意味著明顯困難的問題其實有比較容易的解決方案——當然,，其中的細節(jié)還要麻煩一些,。 實際上,，量子計算機、圖同構問題等人們熱衷的最新進展無不指向P對NP問題,。那么,，P與NP問題究竟是什么？它的解決將意味著什么,？它難在哪里,？量子力學為它帶來了什么？又有什么理論,、將在何時有可能解決它,？本文試圖對這些問題提供簡單的介紹和探討。 圖靈時期的計算機科學關注的主要是問題的可計算性（computability），也即一個問題是否可以被計算機描述并解決,。之后,，隨著可計算性問題的澄清，計算機科學家逐漸將注意力轉移到了另一個問題,，即問題的復雜性（complexity）：執(zhí)行一個給定的算法需要多長時間,？不過，計算機科學家的答案不是幾分鐘或者幾毫秒,，而是所需時間與問題規(guī)模的函數(shù)關系,。 《麻省理工學院新聞》(MIT News）曾發(fā)表過一篇解釋P/NP的文章。這篇文章指出,，想象有一張未經排序的數(shù)字列表,，然后寫一個尋找最大值的算法。首先顯然,，該算法必須要查詢列表中的所有數(shù)字,。但是，如果它只是在每一步查詢一個數(shù)字,，然后只更新并記錄當下的最大數(shù),，那么對于每個數(shù)字，它只需要查詢一次,。于是，該算法的執(zhí)行時間與它處理的問題規(guī)模,，即計算機科學家們所指的N,，直接成正比。當然,，大多數(shù)算法是更為復雜的,，因此比尋找最大值算法的效率要低,。但是有許多常見算法的執(zhí)行時間與N^2，或者N log(N)成正比,。 ?無序數(shù)字列表求最大值的算法示意,。MAX指最大值，N指數(shù)字個數(shù),，a[i]指當前查詢的第i個數(shù)字 一個只包含常數(shù),、N、N^2以及N的其他次方的數(shù)學表達式稱為一個多項式（polynomial）,，這就是“P = NP”中的“P”所代表的單詞,。一般來說，P代表求解時間與N的多項式成正比的問題的集合,。類似地,，PSPACE代表所用空間與N的多項式成正比的問題的集合。 顯然,，一個執(zhí)行時間與N^3成正比的算法的要比與N成正比的算法慢（對于足夠大的N）,，但這種差異與多項式和指數(shù)的差異比起來要渺小得多?！堵槭±砉W院新聞》的這篇文章指出,，如果一個執(zhí)行時間與N成正比的算法用1秒可以解決包含100個輸入元素的問題，那么與N^3成正比的算法大概需要3個小時,。但是,，一個執(zhí)行時間與2^N成正比的算法需要300艾（1艾等于10的18次方）年的時間來解決同樣的問題。所以2^N與N的多項式的差異要比N^3和N之間的差異多的多,。 NP（Nondeterministic Polynomial time,，非確定型多項式時間）指的是其解可以在多項式時間內被驗證的問題集合。容易想象的是,，許多NP問題看起來需要指數(shù)時間來解決,。例如，對于大整數(shù)質因子分解這個或許是NP中最著名的問題,，驗證一個解幾乎只需要做一次乘法,，但要真去解的話似乎需要系統(tǒng)地嘗試大量的可能解。 所以“P是否等于NP”的意思是說“如果一個問題的解可以在多項式時間內被驗證,，那么是否可以在多項式時間內找到這個解”,。這個問題的部分魅力在于，大量典型的看起來需要指數(shù)時間去解決的NP問題被稱為“NP完全問題”（NP-complete,，NPC）,，它們可以在多項式時間內相互轉化。這意味著如果其中一個問題是多項式時間可解的,，那么所有其他問題也都是,。第一個NPC問題是庫克-列文 (Stephen Cook,， Leonid Levin) 給出的布爾可滿足性問題（Boolean Satisfiability problem，SAT）,。于是,，任何NP問題都可以在多項式時間內轉化為SAT問題。與此等價地,，如果SAT在P中,，那么P=NP。這便是著名的庫克-列文定理（Cook–Levin theorem）,。 在現(xiàn)實生活中,，NP完全問題是相當普遍的，特別是在大的調度任務中,?！堵槭±砉W院新聞》曾列舉了一個著名的NP完全問題是所謂的旅行商問題（Traveling Salesman Problem，TSP）,。該問題在當今很發(fā)達的物流業(yè)中可以表述為：一個物流配送公司欲將N個客戶的訂貨沿最短路線全部送到,，那么它應該如何確定最短路線？對于這一問題,，P=NP意味著這樣的物流分配可以很快地進行,，但反之則意味著當物流規(guī)模逐漸擴大時，我們將無法在有效時間內找到最短路線,。 綜上,，我們將P、NP,、NPC以及PSPACE等復雜度類及它們之間相互的關系總結如下圖,。我們還知道，SAT與TSP在NPC中,，而圖同構和大整數(shù)分解等問題既沒有被證明在P中,，也沒能被證明在NPC中，大部分理論計算機科學家認為它們的難度介于P與NPC之間（NP-intermediate,NPI）,。 ?復雜度類關系示意圖,。實線框表示已被證明的真包含關系，虛線框表示尚未被證明的真包含關系（下同） 幾乎沒有一個數(shù)學家、物理學家或者計算機科學家相信P真的等于NP——那樣的話,，所有的密碼將很容易被破解,，很多困擾人們的數(shù)學問題將有辦法被解決，人工智能將突破連連……一個想到答案和驗證答案所需時間相當?shù)氖澜纾瑫俏覀兯娴氖澜鐔?？如果是的話，為什么世界上最聰明的?shù)學家會對著一些數(shù)學問題思索良久,，而當他們想出答案時,，又是那么快地就能驗證答案是否正確呢？既然大多數(shù)人覺得P不等于NP,，那么它的證明究竟有什么用,？研究它又有什么意義？ 麻省理工學院（MIT）數(shù)學系主任以及計算機科學,、人工智能實驗室計算理論小組（Theory of Computation Group,，TOC）成員Michael Sipser認為，P/NP問題有助于我們更加深入地理解計算復雜性,?！耙粋€主要的應用是在密碼學領域，其中密碼安全性經常是由計算任務的復雜性保障的,，”Sipser說,，“互聯(lián)網安全交易常用的RSA加密方案就是研究特定數(shù)論計算復雜性問題時的一個副產品”。此外,，“P/NP問題已經被數(shù)學界的人們廣泛認為是基本,、重要而美麗的數(shù)學問題。我認為它是數(shù)學和計算機科學之間的橋梁,?！?/p> ?Michael Sipser 對于同樣的問題，TOC的另一位成員,、MIT計算機科學和人工智能實驗室副教授Scott Aaronson（現(xiàn)為德克薩斯大學奧斯汀分校計算機科學教授）也提供了他的回答：“是的,，幾乎所有的人都相信P是不等于NP的。但是,，研究這個問題的過程要比結果重要,。這個過程中，為了證明它,，我們將需要大量的對計算的嶄新理解,。我們想要證明的是什么？是對于解決所有這些優(yōu)化問題,、搜索問題,、找到定理的證明、找到航空公司的最佳路線設計,、破解密碼——所有這些不同的東西,，無論你多么聰明，都不能找到有效的算法。所以,，為了證明這樣的命題,，一個先決條件就是要了解所有可能的有效算法組成的空間。這可是一個令人難以置信的艱巨任務,。我們期望的是,，在證明這件事情的過程中，我們會了解到大量的遠超我們想象的關于有效算法的理論,，而且非常非常有可能發(fā)現(xiàn)新的,、當下無法預知的在某些地方有神奇應用的算法。理論計算機科學的歷史經常是這樣的,，你用來證明一些東西不可能的論據(jù)恰恰可以反過來說明別的東西可能,，反之亦然。最簡單的例子是加密,，當你證明一些問題難以被有效解決時,，你也會得到一個有用的編碼方法?！?/p> ?Scott Aaronson 值得一提的是,，在研究P/NP問題時，很多復雜性類的引入有著廣泛而深入的理論意義和實際意義,，有界錯誤概率多項式時間類（bounded-error probabilistic polynomial time,，BPP）便是其中之一。此時不得不提的便是概率算法,。一方面,，20世紀80年代以來很多科學家認為概率的引入有助于解決P/NP問題。另一方面,，如果非要和下文中的量子力學扯上關系,，概率算法是非說不可的——量子算法天然便是概率算法！ 典型的概率算法包含“擲硬幣”的指令,，并且擲硬幣的結果可能影響算法后面的執(zhí)行和輸出,。BPP是這樣的一類判定問題：如果答案是肯定的，那么存在?個多項式時間隨機算法以?于2/3的概率接受,，如果答案是否定的則?于1/3,。換句話說：給定任何輸?，該算法錯誤的概率最多為1/3,。1/3這個數(shù)字的意義僅僅在于它是某個?于1/2的正的常數(shù),。任何這樣的常數(shù)都是?樣好的。為什么呢,？嗯,，假設我們得到?個犯錯概率為1/3的BPP算法,。如果我們真想要的話，我們可以很容易地將這個算法的犯錯概率修改為最多（?如說2^{-100}）,。怎么做呢,？我們僅需要反復運?該算法?百次，然后輸出占多數(shù)的答案,！所以,，這就是BPP：很多人認為，BPP是經典物理學控制的宇宙中計算機可以切實解決的所有問題組成的類,。 BPP與P、NP等的關系如何呢,？顯然,，P包含于BPP，因為P便是不需拋硬幣,、輸出結果確定的BPP,。而現(xiàn)在很多科學家認為，P可能等于BPP,，這是又一個開放性問題,。有趣的是，我們甚至還不知道BPP與NP的關系,，而只知道BPP包含于PSPACE,。因而，下面的關系圖中,，虛線又增多了： ?BPP加入后的復雜度類關系示意圖 看起來,，BPP的加入未必可以解決P/NP問題，反倒帶來了更多尚未有答案的問題,。而事實上,，更多的復雜度類因為研究的需要被引入了進來。在Scott Aaronson開的復雜度類動物園（Complexity Zoo）中,，人們不斷地加入新的復雜度類,，到現(xiàn)在已經有了498只復雜性類！人們不知道這個研究過程何時是個終點,。 綜上所述,，如果P=NP成立，那么世界將換一個模樣,；而如果能夠證明二者不相等,，我們也會取得足夠多的新突破。這正是其重要性所在,。而它很困難的原因恰恰在于,，我們還沒能較為清楚地看到一條通往它的道路,。
“你要是光看報,、讀雜志等,，你可能會覺得一個量子計算機可以通過‘并行地嘗試每一個可能的解’，然后‘在心臟跳一下的時間里解決NP完全問題’,。嗯,，大概那是門外漢們對于量子計算機最核心的錯誤印象?！盨cott Aaronson在接受《麻省理工學院新聞》采訪時說,。 “Peter Shor（另一位TOC成員）發(fā)現(xiàn)大整數(shù)分解的多項式量子算法時，量子計算界確實炸了,?！痹凇堵槭±砉W院新聞》的報道中，Sipser介紹說,?！癙eter的突破引發(fā)了計算機和物理兩個領域的一大波研究。事實上,，Shor的發(fā)現(xiàn)一度點燃了人們利用微觀尺度下反直覺的量子力學來在多項式時間內解決NP完全問題的希望,。但現(xiàn)在看來這似乎不太可能：大整數(shù)分解問題實際上是幾個不知道是否為NP完全的NP困難(NP-hard)問題?！蓖瑯拥?，人們不能證明不存在多項式的大整數(shù)分解算法，所以盡管人們相信量子計算對于大整數(shù)分解這樣的問題會帶來計算能力的提升,，但這點同樣尚未得到證明——更別提對于一般問題的指數(shù)級別的突破了,。 ?Perter Shor 對此，Scott Aaronson介紹了Grover算法作為例子,。Grover算法對于輸入規(guī)模為N的無序數(shù)據(jù)庫給出的~2^{N/2}時間復雜度的量子搜索算法,。但早在Grover的算法之前，Bennett等人已經證明~2^{N/2}是最優(yōu)解了,！換句話說,，任何在2^N那么大的大海中撈一根針的量子算法都需要至少~2^{N/2}步。相應地,，經典計算機需要~2^N步,。所以至少可以說，對于“一般的”或者“無結構的”搜索問題,，量子計算機對于經典計算機來說只能給出某種加速——事實上是平方加速——但不會是像Shor算法那樣的指數(shù)加速,。 為什么這個加速會是平方的，而非立方或者其他什么的,？Scott Aaronson嘗試著給出了答案,，且盡量不牽扯到Grover算法或者Bennett等人最優(yōu)化證明的具體細節(jié),。他認為，從根本上講,，我們得到平方加速的原因是,，量子力學是基于2-范數(shù)而非1-范數(shù)的。經典來講,，如果有N個解,，其中只有一個是正確的，那么查詢一次后我們距離得到正確答案便有了1/N的概率,，查詢兩次后便有了2/N的概率,，查詢三次3/N，依此類推,。因此,，我們需要~N次查詢來獲得足夠大（即接近1）的概率猜出正確答案。但是如果用量子力學,，我們是對一組幾率幅態(tài)矢進行線性變換，它是概率的平方根,。所以我們這樣考慮這個問題：查詢一次后我們有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問題還是需要走很長的路,。 在通往P/NP問題的路上，有很多的嘗試,，例如量子力學,、電路下界、交互式證明技術等,，都先是讓人們看到了希望,，然后隨著研究的深入，又讓人們覺得這些可能還不夠,。那么,，還有什么“有希望的”解決方案嗎？Scott Aaronson介紹了芝加哥大學計算機系教授Ketan Mulmuley的幾何復雜性理論綱領（Geometric Complexity Theory program, GCT program）,。GCT試圖將P/NP問題與代數(shù)幾何,、表示理論等很多看起來比較遠的數(shù)學概念聯(lián)系起來。 ?Ketan Mulmuley “我覺得GCT就像計算機科學領域的弦論,，”Scott Aaronson說,，“一方面，它實現(xiàn)了如此驚人的數(shù)學聯(lián)系,，以至于一旦你看到它們,，你就會覺得這個綱領一定會在正確的道路上。而另一方面,，如果你用已經解決了多少它最初想解決的問題,，而不是這一綱領本身來評價它的話，那么可能它連最初的想法都還沒有實現(xiàn),?！币簿褪钦f，或許正是因為還沒有足夠深入的了解,，所以GCT還保留著解決P/NP的希望,。“甚至GCT綱領最瘋狂的支持者也預測說得有幾十年的跋涉,，而且其在數(shù)學上的復雜性也嚇唬到了其他每個人,。” 是的,，P/NP問題就是這么難,。 感謝Scott Aaronson對本文的意見。 主要參考文獻： 1. MIT News對于Michael Sipser和Scott Aaronson的采訪,，采訪部分獲Scott Aaronson授權翻譯： http://news./2009/explainer-pnp http://news./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.
|
|
|
