從歷史的開端，人類就一直在是解決各種問(wèn)題,。從早期農(nóng)業(yè)到太空探索，解決數(shù)學(xué)問(wèn)題似乎是人類生存的一個(gè)關(guān)鍵因素,。自上世紀(jì)70年代以來(lái)，一些曾經(jīng)單調(diào)乏味的計(jì)算問(wèn)題在一瞬間就可以解決,，這主要是由于計(jì)算能力的指數(shù)級(jí)增長(zhǎng),。然而，一些獨(dú)特的問(wèn)題僅僅通過(guò)技術(shù)進(jìn)步是無(wú)法解決的,，即使對(duì)于最強(qiáng)大的計(jì)算機(jī)來(lái)說(shuō),，解決這些問(wèn)題所花費(fèi)的時(shí)間比人的一生還要長(zhǎng)。事實(shí)上,，現(xiàn)代加密技術(shù)依賴于這樣一個(gè)事實(shí)：大質(zhì)數(shù)不可能因式分解,。這些問(wèn)題似乎都有一個(gè)共同的難題，也就是P（ polynomial time）對(duì)NP（ non-deterministic polynomial time）謎題的核心——什么是可化簡(jiǎn)的,，什么是不可化簡(jiǎn)的,？1859年，愛爾蘭數(shù)學(xué)家威廉·漢密爾頓畫了一個(gè)叫做伊科希的數(shù)學(xué)游戲,。這個(gè)游戲是在一個(gè)由20個(gè)角（頂點(diǎn)）組成的木制十二面體表面上進(jìn)行的,。每個(gè)角落都標(biāo)上了一個(gè)城市的名字。游戲的目標(biāo)是找到一個(gè)循環(huán),，即訪問(wèn)每個(gè)頂點(diǎn)一次,，然后返回起點(diǎn)。這種路徑稱為哈密頓循環(huán),。這個(gè)簡(jiǎn)單的博弈產(chǎn)生了圖論中的一個(gè)重要問(wèn)題,，即哈密頓循環(huán)決策問(wèn)題——給定一個(gè)任意地圖，我們?nèi)绾沃浪欠癜粋€(gè)哈密頓循環(huán),？- 二維平面圖形的十二面體,。一個(gè)可能的哈密頓循環(huán)用紅色表示。
給出一個(gè)圖,，確定它是否包含一個(gè)哈密頓循環(huán),。 解決這個(gè)問(wèn)題的一種方法是遍歷圖中任何可能的路徑,，并檢查該路徑是否為哈密頓循環(huán)。然而,，由于可能路徑的數(shù)量可以達(dá)到n的階乘,。這樣，即使一個(gè)只有40個(gè)頂點(diǎn)的圖也可能包含超過(guò)10^45條路徑,，使得問(wèn)題幾乎不可能在合理的時(shí)間內(nèi)解決(即使對(duì)于最強(qiáng)大的處理器也是如此),。此外，由于頂點(diǎn)數(shù)量與路徑數(shù)量之間的階乘依賴關(guān)系,，即使我們?cè)僭黾右粋€(gè)頂點(diǎn),，也需要大幅提升計(jì)算機(jī)的計(jì)算能力。我們可以說(shuō),，階乘增長(zhǎng)的根本性質(zhì)使這個(gè)問(wèn)題比其他問(wèn)題更困難,。這就是數(shù)學(xué)問(wèn)題的艱巨性——如果一個(gè)問(wèn)題需要的資源隨著投入的增加而急劇增加，那么這個(gè)問(wèn)題就非常棘手,。為了使這個(gè)想法形式化,，計(jì)算機(jī)科學(xué)家使用了時(shí)間復(fù)雜度的尺度。時(shí)間復(fù)雜度指的是解決一個(gè)問(wèn)題需要多少步長(zhǎng),，以及所需的步長(zhǎng)如何隨問(wèn)題的大小而變化,。給定一個(gè)算法，算法的時(shí)間復(fù)雜度被描述為一個(gè)漸近函數(shù),，它依賴于算法的輸入大小,。漸進(jìn)觀點(diǎn)是計(jì)算復(fù)雜性理論所固有的，它揭示了有限而精確的分析所掩蓋的結(jié)構(gòu)——阿維·威格森 - 一個(gè)算法的時(shí)間復(fù)雜度被描述為一個(gè)漸近函數(shù),，它依賴于算法的輸入大小,。一個(gè)主要的區(qū)別是階乘，指數(shù)和多項(xiàng)式復(fù)雜度函數(shù),。
對(duì)于具有多項(xiàng)式復(fù)雜度的算法和具有更基本復(fù)雜度函數(shù)的算法,，有一個(gè)基本的區(qū)別。這種區(qū)別主要是由于多項(xiàng)式增長(zhǎng)被認(rèn)為比其他增長(zhǎng)更為緩慢,，因?yàn)樵龃筝斎氩粫?huì)導(dǎo)致所需步驟急劇增加,。多項(xiàng)式（Polynom）是一種只涉及加、減,、乘和非負(fù)整數(shù)指數(shù)運(yùn)算的構(gòu)造,，因此不是指數(shù)或階乘增長(zhǎng)。選擇多項(xiàng)式來(lái)表示有效的計(jì)算似乎是任意的,，然而,，隨著時(shí)間的推移，它從許多角度證明了自己的合理性,。例如,，多項(xiàng)式在加法,、乘法和組合下的閉包保留了自然編程實(shí)踐中的效率概念，比如將程序鏈接到一個(gè)序列中,，或者將一個(gè)程序嵌套到另一個(gè)程序中具有多項(xiàng)式時(shí)間復(fù)雜度的算法被稱為“高效”,。 多年來(lái)，為了有效地解決哈密頓循環(huán)決策問(wèn)題,，科學(xué)家們進(jìn)行了許多嘗試,。其中一種是Held-Karp算法，它能在指數(shù)時(shí)間內(nèi)解決這個(gè)問(wèn)題,。然而,，沒(méi)有已知的算法可以在多項(xiàng)式時(shí)間內(nèi)解決這個(gè)問(wèn)題，因此,，它仍然被認(rèn)為是一個(gè)難題,。然而,，一個(gè)有趣的現(xiàn)象發(fā)生了，盡管我們不能有效地解決這個(gè)問(wèn)題,，給定一個(gè)路徑圖中，我們至少可以有效地檢查是否是哈密頓循環(huán),，因?yàn)楹?jiǎn)單循環(huán)中的最大頂點(diǎn)數(shù)為n,，則遍歷路徑所需的時(shí)間被多項(xiàng)式限定為n。,。這種現(xiàn)象也出現(xiàn)在其他難題中,，例如數(shù)獨(dú)決策問(wèn)題——給定一個(gè)不完整的數(shù)獨(dú)網(wǎng)格，我們希望知道它是否至少有一個(gè)有效的解決方案,。任何提出的數(shù)獨(dú)解決方案都可以很容易地驗(yàn)證,，并且隨著網(wǎng)格的增大，檢查一個(gè)解決方案的時(shí)間會(huì)多項(xiàng)式的增長(zhǎng),。然而,，所有已知的尋找解決方案的算法，對(duì)于困難的例子,，時(shí)間會(huì)隨著網(wǎng)格的增大呈指數(shù)增長(zhǎng),。與哈密頓路徑?jīng)Q策問(wèn)題相似，目前還沒(méi)有任何已知的算法可以有效地解決數(shù)獨(dú)問(wèn)題,，但是,，只要給出一個(gè)解，就可以有效地驗(yàn)證該解,。似乎許多其他決策問(wèn)題都具有這一特性——不管它們是否能被有效地解決,，它們所提出的解決方案都能被有效地驗(yàn)證,。這類問(wèn)題被定義為NP。如果一個(gè)決策問(wèn)題的解能被有效地驗(yàn)證,，那么這個(gè)決策問(wèn)題就是NP問(wèn)題,。首字母縮寫NP代表不確定性多項(xiàng)式時(shí)間（盡管人們普遍認(rèn)為NP的意思是“非P”）。 進(jìn)一步思考問(wèn)題的可解性與其解的可驗(yàn)證性之間的關(guān)系,，我們可以得出下一個(gè)結(jié)論：如果一個(gè)決策問(wèn)題是有效可解得,，那么它的解必須是有效可驗(yàn)證的。為什么,？因?yàn)槿绻粋€(gè)決策問(wèn)題是可以有效地解決的,，那就意味著我們可以有效地找到它的解決方案。然后,，給出一個(gè)解決方案,，我們可以簡(jiǎn)單地通過(guò)與問(wèn)題的實(shí)際解決方案比較來(lái)驗(yàn)證它。換句話說(shuō),，生成解決方案的算法的正確性自動(dòng)證明了該解決方案,。從這個(gè)結(jié)論可以看出，很明顯,，NP包含的問(wèn)題子集也是有效可解的,。這個(gè)子集被定義為P。- P是所有可有效解決的決策問(wèn)題的集合,，是NP的一個(gè)子集,。基本算法是多項(xiàng)式時(shí)間可解的,。象棋決策問(wèn)題不屬于NP問(wèn)題,，因?yàn)闆](méi)有一種有效的算法可以檢查給定的棋盤是否有效。魔方?jīng)Q策問(wèn)題屬于NP問(wèn)題,，因?yàn)榕袛嘁粋€(gè)給定的魔方是否是一個(gè)解是很簡(jiǎn)單的,。
哈密頓路徑?jīng)Q策問(wèn)題有一個(gè)有效的算法可以驗(yàn)證它的解，因此,，它屬于NP,。有人可能會(huì)問(wèn)這個(gè)問(wèn)題是否在P中，一方面,，我們不知道有一個(gè)有效的算法可以解決這個(gè)問(wèn)題,。另一方面，沒(méi)有證據(jù)表明這樣的算法不存在,。事實(shí)上,，這樣的算法仍然有可能存在，而且還沒(méi)有被發(fā)現(xiàn),。數(shù)獨(dú)的決策問(wèn)題也是一樣,，事實(shí)上,，對(duì)于許多其他主要問(wèn)題，包括布爾可滿足性問(wèn)題,，旅行推銷員問(wèn)題,，子集和問(wèn)題，派系問(wèn)題,，圖著色問(wèn)題——盡管我們已經(jīng)證明這些問(wèn)題是NP,，但沒(méi)有證據(jù)表明他們?cè)赑 。這就是P=NP問(wèn)題的意義所在：P和NP真的是一樣的嗎,？如果是的話,，這就意味著NP中的所有問(wèn)題都可以被有效地解決，盡管我們?nèi)匀粵](méi)有找到實(shí)現(xiàn)這一點(diǎn)的神秘算法,。否則,，在NP中存在一些無(wú)法有效解決的問(wèn)題，任何嘗試解決將意味著浪費(fèi)我們的時(shí)間和精力,。 大多數(shù)時(shí)候,，不能有效地解決問(wèn)題是一件消極的事情。然而,，在某些情況下,，我們可以從問(wèn)題的“硬度”中獲益。屬于NP而不屬于P的問(wèn)題,，其主要特點(diǎn)是很難解決,，但很容易驗(yàn)證其解決方案。給定兩個(gè)正整數(shù)n和k,，判斷n是否有一個(gè)質(zhì)因數(shù)小于k?！|(zhì)因數(shù)分解決策問(wèn)題 由于該問(wèn)題的解可以有效地驗(yàn)證,，因此我們知道該問(wèn)題屬于NP，給定一個(gè)整數(shù)c,，它需要“多項(xiàng)式時(shí)間”來(lái)知道c是否是一個(gè)比k小的質(zhì)數(shù),，還是n的因數(shù)。但是,，目前還沒(méi)有一種算法可以在多項(xiàng)式時(shí)間內(nèi)解決這一問(wèn)題,。因此，使用兩個(gè)相當(dāng)大的質(zhì)數(shù),，就可以計(jì)算它們的乘法,，這用于生成一個(gè)公鑰和一個(gè)私鑰。公鑰可以為所有人所知,，并用于加密消息,。使用公鑰加密的消息只能在合理的時(shí)間內(nèi)使用私鑰解密,，假設(shè)沒(méi)有有效的方法將一個(gè)大整數(shù)分解為它的質(zhì)數(shù)因子。- RSA-2048有617位十進(jìn)制數(shù)字(2048位),。它是RSA數(shù)字中最大的,，因式分解獲得的現(xiàn)金獎(jiǎng)金最高，為20萬(wàn)美元,。除非在不久的將來(lái)在整數(shù)因子分解或計(jì)算能力方面取得重大進(jìn)展,，否則RSA-2048在許多年內(nèi)可能無(wú)法分解。
但是,，如果P=NP,，則最后一個(gè)假設(shè)是錯(cuò)誤的。為什么,？如果P等于NP,，那么質(zhì)因數(shù)分解問(wèn)題在P中，這意味著它可以被有效地解決,。因此,，一旦找到這樣一個(gè)算法，任何公鑰都可以在合理的時(shí)間內(nèi)解密,，而不需要私鑰,，這使得整個(gè)RSA密碼系統(tǒng)完全崩潰，至少在理論上如此,。但是P=NP的負(fù)面影響與它所具有的潛在好處相比,，是無(wú)關(guān)緊要的。在數(shù)學(xué),、優(yōu)化,、人工智能、生物學(xué),、物理學(xué),、經(jīng)濟(jì)學(xué)和工業(yè)領(lǐng)域中，確實(shí)存在著數(shù)以千計(jì)的NP問(wèn)題,，這些問(wèn)題都是出于不同的需要而自然產(chǎn)生的,，而有效的解決方案將使我們?cè)谠S多方面受益。證明P=NP將意味著所有這些難題都可以在多項(xiàng)式時(shí)間內(nèi)解決,，這將導(dǎo)致在那些卓越的算法之后進(jìn)行大規(guī)模的智力追求,。一旦發(fā)現(xiàn)，這些算法將有可能推動(dòng)人類的進(jìn)步,，遠(yuǎn)遠(yuǎn)超出我們的掌握,。- Christian Boehmer Anfinsen是1972年諾貝爾化學(xué)獎(jiǎng)的獲得者之一，因?yàn)樗铝τ谘芯恳环N小的，耐久的100個(gè)氨基酸長(zhǎng)的蛋白質(zhì)核糖核酸酶A的折疊,。該蛋白質(zhì)折疊問(wèn)題是一個(gè)NP問(wèn)題,。
即使這樣的結(jié)果，與解決NP問(wèn)題的有效方法在數(shù)學(xué)本身引起的革命相比,，也可能顯得微不足道,。以著名的畢達(dá)哥拉斯定理為例，該定理闡述了直角三角形的直角邊和斜邊之間的關(guān)系,。這個(gè)定理有370個(gè)已知的證明,。這些證明都是下列決策問(wèn)題的一個(gè)可能的解決方案：“勾股定理是正確的嗎?”這個(gè)想法可以概括為：如果T是一個(gè)定理，p是它的證明,，那么p是決策問(wèn)題的一個(gè)解：“T正確嗎,？” 數(shù)學(xué)定理與決策問(wèn)題之間的這種關(guān)系允許我們推廣關(guān)于P與NP的討論——如果一個(gè)證明的正確性可以在多項(xiàng)式時(shí)間內(nèi)得到驗(yàn)證，那么相應(yīng)的決策問(wèn)題就是NP問(wèn)題（因?yàn)樽C明是對(duì)該決策問(wèn)題提出的解決方案）,。在一個(gè)P等于NP的世界里,，這樣一個(gè)決策問(wèn)題在P中，這意味著它可以用多項(xiàng)式時(shí)間來(lái)解決,。解決這樣一個(gè)決策問(wèn)題本質(zhì)上就是找到定理T的證明,。這可能意味著，在某種程度上,，證明一個(gè)數(shù)學(xué)定理并不比檢查一個(gè)給定證明的正確性難多少,。P = NP可能意味著證明一個(gè)數(shù)學(xué)定理從根本上來(lái)說(shuō)并不比驗(yàn)證其證明的正確性更難。 最后的結(jié)論是值得注意的,，因?yàn)槊恳粋€(gè)數(shù)學(xué)證明都可以形式化為一系列定義良好的邏輯陳述,，并由計(jì)算機(jī)程序進(jìn)行處理，自動(dòng)驗(yàn)證證明,。因此,，P = NP意味著證明數(shù)學(xué)定理可以用一個(gè)簡(jiǎn)單的計(jì)算機(jī)程序來(lái)完成。“P = NP可以通過(guò)允許計(jì)算機(jī)找到任何定理的形式證明來(lái)改變數(shù)學(xué),，只要這個(gè)定理能證明一個(gè)合理的長(zhǎng)度,，因?yàn)樾问阶C明可以在多項(xiàng)式時(shí)間內(nèi)很容易地被識(shí)別出來(lái)?！薄沟俜摇?kù)克 人們認(rèn)為P=NP不太可能的一個(gè)心理原因是，提出數(shù)學(xué)定理這樣的任務(wù)通常需要一定程度的創(chuàng)造力,，而我們并不指望一個(gè)簡(jiǎn)單的計(jì)算機(jī)程序具有這種創(chuàng)造力,。我們欣賞維爾斯關(guān)于費(fèi)馬最后定理的證明以及牛頓，愛因斯坦,，達(dá)爾文,，沃森和克里克的科學(xué)理論，欣賞金門大橋和金字塔的設(shè)計(jì),，有時(shí)甚至是赫爾克里·波洛和馬普爾小姐對(duì)謀殺案的分析,。正是因?yàn)樗麄兯坪跣枰粋€(gè)飛躍,，這不是每個(gè)人都能做到的，更不用說(shuō)簡(jiǎn)單的機(jī)械設(shè)備了——阿維·威格森 以上的觀點(diǎn)讓我們開始討論人類大腦的本質(zhì),。雖然科學(xué)離理解大腦的機(jī)制還很遙遠(yuǎn),，但物理定律控制著它的行為。因此,，就像其他自然過(guò)程一樣,，大腦是一種高效的計(jì)算設(shè)備。因此,，任何解決任何問(wèn)題的方法只要被大腦識(shí)別,，就可以被有效地識(shí)別。因此,，P=NP可能意味著大腦有能力以同樣的效率解決這些問(wèn)題,。
如果P = NP，那么任何人類或計(jì)算機(jī)都將擁有傳統(tǒng)上被認(rèn)為是神的那種推理能力,，這似乎很難接受,。 對(duì)于大多數(shù)人來(lái)說(shuō)，像懷爾斯對(duì)費(fèi)馬最后定理的證明或愛因斯坦的相對(duì)論這樣的驚人發(fā)現(xiàn)可以由一個(gè)沒(méi)有頭腦的機(jī)器人產(chǎn)生是不可能的,，因?yàn)樗麄兌加幸粋€(gè)強(qiáng)烈的觀點(diǎn),，即創(chuàng)造力對(duì)于獲得這樣的見解是絕對(duì)必要的。如果P=NP,，那么這個(gè)世界將是一個(gè)與我們通常假設(shè)的完全不同的地方,。每個(gè)能欣賞交響樂(lè)的人都會(huì)是莫扎特?！薄狝vi Wigderson 復(fù)雜性理論家普遍認(rèn)為P不等于NP,，這樣一個(gè)美麗的世界是不可能存在的。2000年,，克萊數(shù)學(xué)研究所將P與NP問(wèn)題列為數(shù)學(xué)中七個(gè)最重要的開放問(wèn)題之一,，并為能證明P是否等于NP的問(wèn)題提供了100萬(wàn)美元的獎(jiǎng)金。
|
