【原】解決計算機數(shù)學(xué)中最著名的難題（P=NP）將徹底改變?nèi)祟愇拿鬟M(jìn)程

老胡說科學(xué) 2021-05-10

展開全文

從歷史的開端，人類就一直在是解決各種問題。從早期農(nóng)業(yè)到太空探索，解決數(shù)學(xué)問題似乎是人類生存的一個關(guān)鍵因素。自上世紀(jì)70年代以來，一些曾經(jīng)單調(diào)乏味的計算問題在一瞬間就可以解決，這主要是由于計算能力的指數(shù)級增長。然而，一些獨特的問題僅僅通過技術(shù)進(jìn)步是無法解決的，即使對于最強大的計算機來說，解決這些問題所花費的時間比人的一生還要長。事實上，現(xiàn)代加密技術(shù)依賴于這樣一個事實：大質(zhì)數(shù)不可能因式分解。這些問題似乎都有一個共同的難題，也就是P（ polynomial time）對NP（ non-deterministic polynomial time）謎題的核心——什么是可化簡的，什么是不可化簡的？

1859年，愛爾蘭數(shù)學(xué)家威廉·漢密爾頓畫了一個叫做伊科希的數(shù)學(xué)游戲。這個游戲是在一個由20個角（頂點）組成的木制十二面體表面上進(jìn)行的。每個角落都標(biāo)上了一個城市的名字。游戲的目標(biāo)是找到一個循環(huán)，即訪問每個頂點一次，然后返回起點。這種路徑稱為哈密頓循環(huán)。這個簡單的博弈產(chǎn)生了圖論中的一個重要問題，即哈密頓循環(huán)決策問題——給定一個任意地圖，我們?nèi)绾沃浪欠癜粋€哈密頓循環(huán)？

二維平面圖形的十二面體。一個可能的哈密頓循環(huán)用紅色表示。

給出一個圖，確定它是否包含一個哈密頓循環(huán)。

解決這個問題的一種方法是遍歷圖中任何可能的路徑，并檢查該路徑是否為哈密頓循環(huán)。然而，由于可能路徑的數(shù)量可以達(dá)到n的階乘。這樣，即使一個只有40個頂點的圖也可能包含超過10^45條路徑，使得問題幾乎不可能在合理的時間內(nèi)解決(即使對于最強大的處理器也是如此)。此外，由于頂點數(shù)量與路徑數(shù)量之間的階乘依賴關(guān)系，即使我們再增加一個頂點，也需要大幅提升計算機的計算能力。我們可以說，階乘增長的根本性質(zhì)使這個問題比其他問題更困難。這就是數(shù)學(xué)問題的艱巨性——如果一個問題需要的資源隨著投入的增加而急劇增加，那么這個問題就非常棘手。

為了使這個想法形式化，計算機科學(xué)家使用了時間復(fù)雜度的尺度。時間復(fù)雜度指的是解決一個問題需要多少步長，以及所需的步長如何隨問題的大小而變化。給定一個算法，算法的時間復(fù)雜度被描述為一個漸近函數(shù)，它依賴于算法的輸入大小。

漸進(jìn)觀點是計算復(fù)雜性理論所固有的，它揭示了有限而精確的分析所掩蓋的結(jié)構(gòu)——阿維·威格森

一個算法的時間復(fù)雜度被描述為一個漸近函數(shù)，它依賴于算法的輸入大小。一個主要的區(qū)別是階乘，指數(shù)和多項式復(fù)雜度函數(shù)。

對于具有多項式復(fù)雜度的算法和具有更基本復(fù)雜度函數(shù)的算法，有一個基本的區(qū)別。這種區(qū)別主要是由于多項式增長被認(rèn)為比其他增長更為緩慢，因為增大輸入不會導(dǎo)致所需步驟急劇增加。多項式（Polynom）是一種只涉及加、減、乘和非負(fù)整數(shù)指數(shù)運算的構(gòu)造，因此不是指數(shù)或階乘增長。選擇多項式來表示有效的計算似乎是任意的，然而，隨著時間的推移，它從許多角度證明了自己的合理性。例如，多項式在加法、乘法和組合下的閉包保留了自然編程實踐中的效率概念，比如將程序鏈接到一個序列中，或者將一個程序嵌套到另一個程序中

具有多項式時間復(fù)雜度的算法被稱為“高效”。

多年來，為了有效地解決哈密頓循環(huán)決策問題，科學(xué)家們進(jìn)行了許多嘗試。其中一種是Held-Karp算法，它能在指數(shù)時間內(nèi)解決這個問題。然而，沒有已知的算法可以在多項式時間內(nèi)解決這個問題，因此，它仍然被認(rèn)為是一個難題。

邁克爾·赫爾德，理查德·史克和理查德·卡普。

然而，一個有趣的現(xiàn)象發(fā)生了，盡管我們不能有效地解決這個問題，給定一個路徑圖中，我們至少可以有效地檢查是否是哈密頓循環(huán)，因為簡單循環(huán)中的最大頂點數(shù)為n，則遍歷路徑所需的時間被多項式限定為n。。

這種現(xiàn)象也出現(xiàn)在其他難題中，例如數(shù)獨決策問題——給定一個不完整的數(shù)獨網(wǎng)格，我們希望知道它是否至少有一個有效的解決方案。任何提出的數(shù)獨解決方案都可以很容易地驗證，并且隨著網(wǎng)格的增大，檢查一個解決方案的時間會多項式的增長。然而，所有已知的尋找解決方案的算法，對于困難的例子，時間會隨著網(wǎng)格的增大呈指數(shù)增長。與哈密頓路徑?jīng)Q策問題相似，目前還沒有任何已知的算法可以有效地解決數(shù)獨問題，但是，只要給出一個解，就可以有效地驗證該解。似乎許多其他決策問題都具有這一特性——不管它們是否能被有效地解決，它們所提出的解決方案都能被有效地驗證。這類問題被定義為NP。

如果一個決策問題的解能被有效地驗證，那么這個決策問題就是NP問題。

首字母縮寫NP代表不確定性多項式時間（盡管人們普遍認(rèn)為NP的意思是“非P”）。

進(jìn)一步思考問題的可解性與其解的可驗證性之間的關(guān)系，我們可以得出下一個結(jié)論：如果一個決策問題是有效可解得，那么它的解必須是有效可驗證的。為什么？因為如果一個決策問題是可以有效地解決的，那就意味著我們可以有效地找到它的解決方案。然后，給出一個解決方案，我們可以簡單地通過與問題的實際解決方案比較來驗證它。換句話說，生成解決方案的算法的正確性自動證明了該解決方案。從這個結(jié)論可以看出，很明顯，NP包含的問題子集也是有效可解的。這個子集被定義為P。

P是所有可有效解決的決策問題的集合，是NP的一個子集?；舅惴ㄊ嵌囗検綍r間可解的。象棋決策問題不屬于NP問題，因為沒有一種有效的算法可以檢查給定的棋盤是否有效。魔方?jīng)Q策問題屬于NP問題，因為判斷一個給定的魔方是否是一個解是很簡單的。

哈密頓路徑?jīng)Q策問題有一個有效的算法可以驗證它的解，因此，它屬于NP。有人可能會問這個問題是否在P中，一方面，我們不知道有一個有效的算法可以解決這個問題。另一方面，沒有證據(jù)表明這樣的算法不存在。事實上，這樣的算法仍然有可能存在，而且還沒有被發(fā)現(xiàn)。數(shù)獨的決策問題也是一樣，事實上，對于許多其他主要問題，包括布爾可滿足性問題，旅行推銷員問題，子集和問題，派系問題，圖著色問題——盡管我們已經(jīng)證明這些問題是NP，但沒有證據(jù)表明他們在P 。這就是P=NP問題的意義所在：

P和NP真的是一樣的嗎？如果是的話，這就意味著NP中的所有問題都可以被有效地解決，盡管我們?nèi)匀粵]有找到實現(xiàn)這一點的神秘算法。否則，在NP中存在一些無法有效解決的問題，任何嘗試解決將意味著浪費我們的時間和精力。

大多數(shù)時候，不能有效地解決問題是一件消極的事情。然而，在某些情況下，我們可以從問題的“硬度”中獲益。屬于NP而不屬于P的問題，其主要特點是很難解決，但很容易驗證其解決方案。

給定兩個正整數(shù)n和k，判斷n是否有一個質(zhì)因數(shù)小于k?！|(zhì)因數(shù)分解決策問題

由于該問題的解可以有效地驗證，因此我們知道該問題屬于NP，給定一個整數(shù)c，它需要“多項式時間”來知道c是否是一個比k小的質(zhì)數(shù)，還是n的因數(shù)。但是，目前還沒有一種算法可以在多項式時間內(nèi)解決這一問題。因此，使用兩個相當(dāng)大的質(zhì)數(shù)，就可以計算它們的乘法，這用于生成一個公鑰和一個私鑰。公鑰可以為所有人所知，并用于加密消息。使用公鑰加密的消息只能在合理的時間內(nèi)使用私鑰解密，假設(shè)沒有有效的方法將一個大整數(shù)分解為它的質(zhì)數(shù)因子。

RSA-2048有617位十進(jìn)制數(shù)字(2048位)。它是RSA數(shù)字中最大的，因式分解獲得的現(xiàn)金獎金最高，為20萬美元。除非在不久的將來在整數(shù)因子分解或計算能力方面取得重大進(jìn)展，否則RSA-2048在許多年內(nèi)可能無法分解。

但是，如果P=NP，則最后一個假設(shè)是錯誤的。為什么？如果P等于NP，那么質(zhì)因數(shù)分解問題在P中，這意味著它可以被有效地解決。因此，一旦找到這樣一個算法，任何公鑰都可以在合理的時間內(nèi)解密，而不需要私鑰，這使得整個RSA密碼系統(tǒng)完全崩潰，至少在理論上如此。

但是P=NP的負(fù)面影響與它所具有的潛在好處相比，是無關(guān)緊要的。在數(shù)學(xué)、優(yōu)化、人工智能、生物學(xué)、物理學(xué)、經(jīng)濟(jì)學(xué)和工業(yè)領(lǐng)域中，確實存在著數(shù)以千計的NP問題，這些問題都是出于不同的需要而自然產(chǎn)生的，而有效的解決方案將使我們在許多方面受益。證明P=NP將意味著所有這些難題都可以在多項式時間內(nèi)解決，這將導(dǎo)致在那些卓越的算法之后進(jìn)行大規(guī)模的智力追求。一旦發(fā)現(xiàn)，這些算法將有可能推動人類的進(jìn)步，遠(yuǎn)遠(yuǎn)超出我們的掌握。

Christian Boehmer Anfinsen是1972年諾貝爾化學(xué)獎的獲得者之一，因為他致力于研究一種小的，耐久的100個氨基酸長的蛋白質(zhì)核糖核酸酶A的折疊。該蛋白質(zhì)折疊問題是一個NP問題。

即使這樣的結(jié)果，與解決NP問題的有效方法在數(shù)學(xué)本身引起的革命相比，也可能顯得微不足道。

以著名的畢達(dá)哥拉斯定理為例，該定理闡述了直角三角形的直角邊和斜邊之間的關(guān)系。這個定理有370個已知的證明。這些證明都是下列決策問題的一個可能的解決方案：“勾股定理是正確的嗎?”這個想法可以概括為：

如果T是一個定理，p是它的證明，那么p是決策問題的一個解：“T正確嗎？”

數(shù)學(xué)定理與決策問題之間的這種關(guān)系允許我們推廣關(guān)于P與NP的討論——如果一個證明的正確性可以在多項式時間內(nèi)得到驗證，那么相應(yīng)的決策問題就是NP問題（因為證明是對該決策問題提出的解決方案）。在一個P等于NP的世界里，這樣一個決策問題在P中，這意味著它可以用多項式時間來解決。解決這樣一個決策問題本質(zhì)上就是找到定理T的證明。這可能意味著，在某種程度上，證明一個數(shù)學(xué)定理并不比檢查一個給定證明的正確性難多少。

P = NP可能意味著證明一個數(shù)學(xué)定理從根本上來說并不比驗證其證明的正確性更難。

最后的結(jié)論是值得注意的，因為每一個數(shù)學(xué)證明都可以形式化為一系列定義良好的邏輯陳述，并由計算機程序進(jìn)行處理，自動驗證證明。因此，P = NP意味著證明數(shù)學(xué)定理可以用一個簡單的計算機程序來完成。

“P = NP可以通過允許計算機找到任何定理的形式證明來改變數(shù)學(xué)，只要這個定理能證明一個合理的長度，因為形式證明可以在多項式時間內(nèi)很容易地被識別出來?！薄沟俜摇炜?/span>

人們認(rèn)為P=NP不太可能的一個心理原因是，提出數(shù)學(xué)定理這樣的任務(wù)通常需要一定程度的創(chuàng)造力，而我們并不指望一個簡單的計算機程序具有這種創(chuàng)造力。

我們欣賞維爾斯關(guān)于費馬最后定理的證明以及牛頓，愛因斯坦，達(dá)爾文，沃森和克里克的科學(xué)理論，欣賞金門大橋和金字塔的設(shè)計，有時甚至是赫爾克里·波洛和馬普爾小姐對謀殺案的分析。正是因為他們似乎需要一個飛躍，這不是每個人都能做到的，更不用說簡單的機械設(shè)備了——阿維·威格森

以上的觀點讓我們開始討論人類大腦的本質(zhì)。雖然科學(xué)離理解大腦的機制還很遙遠(yuǎn)，但物理定律控制著它的行為。因此，就像其他自然過程一樣，大腦是一種高效的計算設(shè)備。因此，任何解決任何問題的方法只要被大腦識別，就可以被有效地識別。因此，P=NP可能意味著大腦有能力以同樣的效率解決這些問題。