如果「P = NP」得到證明，意味著什麼？

01-03

如果p=np被證明為真，對非相關專業領域的民眾有什麼直接影響

如果某天發現 NP=P，或者弱一點的 NP=BPP，對密碼學（以及計算理論的很多領域）來說當然是個壞消息。但這並不意味著整個領域會無事可做，PhD 也失業跳樓

如果 NP=P，基本意味這對任何實用的加密系統，存在一個正整數 k，有一個運行時間是 $O(x^k)$ 的演算法可以攻破它。但是沒關係，只要這個 k 足夠大，其實對安全性沒什麼影響

P: 老闆，我找到一個多項式時間演算法可以破解 RSA

A: 太棒了！不要告訴別人！我們一起搶銀行吧！運行時間是多少？

P: $n^{3underbrace{uparrowuparrowldotsuparrowuparrow}_{3uparrowuparrowuparrowuparrow3}3}$

A: ′_ゝ`) 還是老實發 paper 吧

如果NP完全問題被解決了，你點菜時就不用為價格煩惱了！

=======好吧，這是個梗，以下正文=======

如果NP問題被實質性地解決，整個世界的數字化信息都將被其顛覆！就從應用非常廣泛的非對稱加密演算法來講，其安全性正是建立在NP問題無法被轉換成P問題的基礎上。

比方說最常用的非對稱加密RSA，如果我們知道一組公鑰 ${n,e}$ ，想將對應的私鑰計算出來，理論上只要對 $n$ 進行質因數分解得到 $r_{1}, r_{2}$ ，就能算出 $varphi (n)=(r_{1}-1)(r_{2}-1)$ ，然後找到一個整數 $k$ 使得 $d = frac{kvarphi (n)+1}{e}$ 也為整數，我們就得到了私鑰 ${n,d}$ 。

這裡最關鍵的一步就是大數的質因數分解，傳統的演算法最高效也只能達到 $O(n)=e^{1.9sqrt[3]{log n(log log n)^2}}$ (General number field sieve, GNFS)，這是一個半指數函數，但仍然是屬於NP問題的範疇。然而利用量子計算技術卻能將這個過程優化為 $O(n)=(log n)^3$ (Shor"s_algorithm)！這簡直就是駭人聽聞！如果這個演算法被實現了，那麼如今被廣泛應用的一切加密手段都將受到嚴重威脅！

Derivatives of Shor"s algorithm are widely conjectured to be
effective against all mainstream public-key algorithms including RSA,
Diffie-Hellman and elliptic curve cryptography. According to Professor Gilles
Brassard, an expert in quantum computing: "The time needed to factor an
RSA integer is the same order as the time needed to use that same integer as
modulus for a single RSA encryption. In other words, it takes no more time to
break RSA on a quantum computer (up to a multiplicative constant) than to use
it legitimately on a classical computer."
(Key size, Wikipedia)

慶幸的是如今的量子計算機還未能發展到計算如此複雜問題的程度，RSA如無意外的話在接下來很長一段時間內還不會受到量子計算的威脅。(Now that quantum computers have been out for a while, has RSA been cracked?)

然而，如果能夠從理論的角度解決NP完全問題，那麼不用等別的什麼技術的發展了，所有的信息安全系統都將形同虛設。

對非相關專業領域的民眾有什麼直接影響？

路人鉀：等等，似乎我們平時買菜的時候不會考慮到類似的問題耶，那NP問題有沒有被證明關我們什麼事？

R君：你說得對，就算它被證明了也影響不了你們的正常生活，但是它會改變你們身邊一切的事物。想想看銀行要是沒有可靠的保密手段，還怎麼得到客戶的信任？你們會逐漸學會考慮信息安全可能給自己帶來的影響，重新評估各種信息媒介、儲蓄服務的信任度和風險度，從而協助管理自己的投資理財、選擇信息渠道、保護個人隱私等等。

路人鈣：但是這些問題不是應該由那些程序猿們來解決嗎？我們只要更新我們的客戶端就行了啊。

R君：程序猿們巴不得NP問題早日被人證明，還會為此大肆慶祝一番，說不定還會定下程序猿解放紀念日之類的……NP問題要是被解決了，現今的諸多技術都將受到安全威脅，然而新的安全技術需要依靠一大群數學家和計算機科學家的研究，不是短時間能被解決的。因此很有可能出現一個過渡階段，在這個階段中用戶則是受到影響最大的群體，諸多的信息服務可能因安全考慮直接暫停，你還怎麼更新客戶端？銀行的電子系統也可能面臨威脅，說不定那時候就只能使用現今交易了。

路人鋅：那我們怎麼辦啊？

R君：偉大的飛面大神會帶領你們脫離苦海的。RAmen

那我就不用讀PhD了，直接轉行算了……（想想其實也很不錯呢 &>_&<

我導師估計也要失業了

而且目測整個歐美學術圈theory組暫時都沒什麼正事可以做了，大部分和計算複雜性相關領域的研究都失去了意義

之前發的什麼Godel獎、Nevanlinna獎大多數也都是廢紙了，什麼Probabilistically Checkable Proof，什麼Unique Games Conjecture這些所謂的重要研究都是nonsense了

不過數學界的機械化證明目測就要成為主流（這麼看其實大部分數學家也要失業了？

（我在原答案中不假思索地隨手敲出了上面這句話，但實際上這是不對的，即使P=NP也未必是機械化證明成為主流，沒有任何證據證明數學命題的證明屬於NP範疇，而且就算我們有多項式演算法判斷一個數學命題的正確與否，so what？根本不能和找到一個證明的重要性和意義相提並論。

然而我意識到我寫這句話是受到了很多其他科普文章的影響，所以我現在覺得解釋一下這件事情很重要，說三遍：

上面這句話是不對的，沒有任何證據表明判斷數學命題正確與否屬於NP範疇，更何況判斷一個數學命題正確與否根本比不上找出一個證明

上面這句話是不對的，沒有任何證據表明判斷數學命題正確與否屬於NP範疇，更何況判斷一個數學命題正確與否根本比不上找出一個證明）

當然以上都是相關專業領域，對於普通民眾來說，

說不定人類就要進入一個新時代了

我也很難想像以後的生活，畢竟信仰崩塌了再重建是非常辛苦的，

但普通人的生活也會在短時間內有翻天覆地的變化應該是肯定的了。

有人提到某門課不用考試了。。就我的感覺，許多課都可以不用考試了。。。。。

還有，大概許多理論計算機科學家發的許多paper變得nonsense了吧

老師說過，NP問題一旦解決，全世界軟體從業人員放假三天以示慶賀

具體參看果殼網死理性派這篇文章。已經說的很白話了。

P vs. NP：從一則數學家謀殺案說起

Market is efficient.

意味著我之前做的所有工作都白費了，犯了方向性的錯誤……

我一直在證P ≠ NP……

註：這篇文章寫的略誇張，因為即使證明了P=NP，我們可以將一個複雜度為指數的演算法變成一個複雜度為多項式的演算法也並不能說明這個多項式演算法很快。即使同是多項式演算法，因為非確定型圖靈機在現實中是不存在的，在計算機上運行時也不能認為他們「同樣容易」。但這篇文章寫的很有意思，大家不妨一看。

——————————————————————————————————————————

M67寫了一篇文章很好的闡述了P=NP所可能帶來的影響：

引用自：假如P=NP，世界將會怎樣？

在計算機複雜度理論中，P問題指的是能夠在多項式的時間裡得到解決的問題，NP問題指的是能夠在多項式的時間裡驗證一個解是否正確的問題。雖然人們大多相信P問題不等於NP問題，但人們目前既不能證明它，也不能推翻它。P是否等於NP是計算機科學領域中最突出的問題，在千禧年七大難題中排在首位。科學家們普遍認為P≠NP是有原因的。讓我們來看一看，如果哪一天科學家證明了P=NP，尋找一個解和驗證一個解變得同樣容易，那這個世界將會變得怎樣？
已知的NPC難題將全部獲解，這將瞬間給各個科學領域都帶來革命性的進展。整數規劃、01規劃、背包問題全部獲解，運籌學將登上一個全新的高度；資料庫的串列化、多處理器調度等問題也隨之解決，大大提高了計算機的性能。同時，空當接龍、掃雷、數獨等經典遊戲也由於獲得了多項式的演算法而在很大程度上失去了意義。
演算法研究方向將發生全面轉移。對演算法的研究可能會轉向圍棋等NP-Hard問題。演算法設計的學問與「NP問題統一解」的關係正如小學應用題與列方程解題的關係一樣，將成為一種純粹鍛煉思維的遊戲。
一些新型的自動編程語言將出現，並將逐漸取代傳統的編程語言。這種新型編程語言扮演著一個「判定性/最優化問題萬能解決器」的角色。在新的編程語言中，你只需要用代碼指明輸入數據與輸出數據的關係，而無需關心計算輸出數據的步驟。只要這種關係是多項式時間內可計算的，編譯器將自動找到解法。在新型編程語言的支持下，人們唯一需要考慮的是，如何把實際問題轉化成數學模型。
利用Occam剃刀原理，困擾人類已久的自然語言處理問題將被一舉攻破。只要提供足夠多的語言文字材料，計算機將很快掌握這門語言，並反過來為語言學提供新的科學體系。考慮這樣一個最優化問題：輸入一大批語句樣本，它們有的符合語法，有的不符合語法；尋找一個最簡單的演算法，將這些語句輸入這個演算法時，演算法能正確得出它是否符合語法。顯然，這個問題本身是NP的（當然前提是該演算法是多項式的），因此計算機可以在多項式時間內找到能判定語法正誤的最簡演算法。我們有理由相信，這個演算法也就是人類頭腦中正在使用的演算法，因此它能夠適用於所給材料之外的其它語句，並具有自我學習的功能。分詞技術、手寫識別、語音朗讀、語音識別等難題在一瞬間全部攻破。
很可能計算機給出的自然語言處理演算法完全不同於傳統語言學的那一套方法，因此傳統語言學本身將受到極大的衝擊。字、詞、句的概念很可能被重新界定，詞類、句式的概念有可能被完全顛覆。
類似地，所有人工智慧問題都將得到解決。我們只需要向計算機提交足夠多的情境以及與之對應的正常人反應，計算機就可以找出一種能正確生成出這些反應的最簡演算法，並且由我們的Occam剃刀假設，這種演算法能夠適用於更廣的範圍，完全模仿人類的行為。在網路上，再沒有任何辦法能夠把計算機和人區別開來。驗證碼將變得毫無意義。

計算機不僅能輕易通過圖靈測試，還能精確地模仿某一個特定的人。如果你能把某個人的網路聊天記錄全部搜集起來，把這個人和網友們的對話全部遞交給計算機，計算機將會很快學會如何模仿這個人。網路的身份鑒定將變得相當困難，很可能不得不藉助一些物理方式。
數學證明可以完全交給計算機來處理。尋找一個反例和驗證一個反例變得同樣簡單，一切錯誤的猜想都將瞬間被推翻。事實上，尋找一個數學證明和驗證一個證明的正確性也變得同樣簡單，因此一切正確的命題也能夠瞬間找到一個最簡的證明。困擾人類數個世紀的數學猜想將逐一獲解。數學領域內部將掀起一次革命，數學研究真正成為了一門「提出問題的藝術」而不再是「解決問題的藝術」。數理邏輯等底層研究，以及開創數學新分支並將其形式化，將成為數學研究的主流方向。
類似地，一切具有解釋性並可以形式化的科學都可以藉助計算機尋求現象的最佳解釋方案。物理學、化學、經濟學、心理學等學科都將會受到不同程度的影響。
md5演算法不再有效，判定一個串的md5是否等於給定值與尋找一個md5等於給定值的串一樣輕鬆。RSA演算法也不再有效，尋找一個質因子和判斷整除性也變得一樣簡單。事實上，發明任何新的密碼演算法都是徒勞——計算機可以根據一大批明文密文樣本推算出生成密文的演算法（只要這個演算法是多項式的）。現有的密碼學體系徹底崩潰。理論上不具有可預測性的一次一密協議成為唯一安全的密碼協議。但人們很快注意到，密碼本本身的生成也不能依賴於任何偽隨機數演算法，必須完全藉助於物理演算法。從這個角度來說，純機器的密碼協議將不復存在，任何身份驗證手續都必須藉助物理手段。互聯網可能會變得非常不可靠。
本人對複雜度理論涉獵不深，並且敘述頗有些誇大其辭，歡迎網友們探討、指正、爭論和補充。
本文部分參考一篇牛文，已上傳至我的空間，強烈建議大家膜拜：http://www.matrix67.com/data/average.ps

對於一般人最大的影響當然是你們的錢暫時都變的不安全了啊！

因為現有的加密演算法都能被破解了哦！

我說個片面的回答吧。

現代密碼學，現實中用的好多加密演算法，核心都是歸結到NP不可解上的。

RSA演算法就是，不可逆的地方在於兩個大質數相乘的結果，如果只知道結果而不知道那兩個素數，想把這兩個素數找出來，那是非常難的，屬於NP問題。

對普通人來說，網銀不再安全了。

意味著n等於1，或者p等於0

1.對運籌學的影響

上圖的意思是如果NP完全問題被解決了，那麼你點菜的時候就再也不用苦惱了！因為，點菜的選擇優化問題是一個NP完全問題。

如果P=NP被證明，那運籌學中的很多難題都將被輕鬆解決，比如說整數規劃問題、旅行商問題等等，整個運籌學會被提升到一個難以想像的高度。運籌學的主要研究方向可能會轉向NP難問題。

2.對密碼學的影響

很多密碼會被破解。現代密碼學，現實中用的好多加密演算法，核心都是歸結到NP不等於P上的。如果我們找到了多項式時間演算法，很多密碼的破解時間會被大大減少。其中RSA演算法就是，不可逆的地方在於兩個大質數相乘的結果，如果只知道結果而不知道那兩個素數，想把這兩個素數找出來，那是非常難的，屬於NP問題。

我們的密碼將不再安全。如果該問題被解決，我們的密碼學會出現很長一段的不安全期。如果該問題真的被解決，我們需要採取的加密方案必須是在NP問題以外的問題。

3.對數學的影響

如果P=NP被證明的話，現在做理論研究的數學家可能有很大一部分要失業了。為什麼呢？我們來看NP完全理論奠基人史提芬·古克的一段話：「P=NP會將數學轉變為讓計算機對任何問題尋找擁有合理長度的證明的學科，因為我們能夠在多項式時間內驗證一個證明是否正確。這些問題也正好包括千禧年大獎的那些問題。」

因此，尋找一個反例和驗證一個反例變得同樣簡單，一切錯誤的猜想都將瞬間被推翻。事實上，尋找一個數學證明和驗證一個證明的正確性也變得同樣簡單，因此一切正確的命題也能夠瞬間找到一個最簡的證明。所以，原來的理論數學家的工作會發生巨大的轉變。他們不再需要考慮如何去證明一個猜想或一個定理，他們只需要提出猜想！

P = 1或者 N = 0.

好把上面是個梗。

說正經的，P是一系列問題的集合，這些問題都能夠讓一台確定性圖靈機在多項式時間內解決。

NP也是一系列問題的集合，這些問題能夠讓一台非確定性圖靈機在多項式時間中解決。

簡單的說，你可以認為一台非確定性圖靈機的計算能力等價於無數台確定性圖靈機並行在一起。或者用一個更形象地例子，一台非確定性圖靈機就像一台有著無數個CPU的計算機——這顯然是不可能真正存在於世上的——那麼這樣的一台計算機能夠在多項式時間中解決的問題，能不能被轉換成一台普通計算機在多項式時間內解決的問題？

如果可以，那麼P等於NP，如果不行，P不等於NP。

你大概會覺得：這NM不是坑呢么！怎麼可能等於！

事實上大部分研究者也是這麼認為的，目前大家的看法基本上就是P ！=NP。

另外順便說一下，某種角度上講，目前正在不斷展開各種研究的量子計算機就是對非確定性圖靈機的一種模擬。因為量子計算機使用量子作為計算單元，一台量子計算機中存在的核心數量將非常大，某種程度上近乎於無窮，即在一定程度上可以模擬非確定性圖靈機。

而如果P真的被證明等於NP（雖然這怎麼想怎麼不可能），那麼這意味著我們之前使用的演算法中有一大批都是可以繼續提高效率的，計算時間（至少是理論上）會被大大縮短，使用計算機的行業效率會急劇上升——會傷心的大概只有密碼學，不過即使P=PN被證明為假，為了應付量子計算機他們也得研究新的演算法……

大概就是這麼個感覺吧。

想起來 Knuth 在一次訪談里有提到，他隱隱傾向於 P = NP ，然而即使 P = NP，我們也並不能輕易找到一個 P 命題對應的 NP 命題。等價性的確認，並不一定意味著困難的降低。

證出來沒關係~大家就開始去做PSPACE-hard的問題了吧~

再被證出來了還有EXPSPACE……或者玩kolmogorov complexity

其實現在做複雜度的好像也沒多少人做P＝NP，影響不大吧……這個證出來倒是拆了一堆做近似演算法組合優化FPT什麼的人的台

做複雜度的永遠不會失業吧……永遠可以自己定義出來新的

當然經費沒有了是另一回事。。。

這個問題絕對會在近幾年內被解決！

現在的機器智能都是利用分散式演算法+密集計算資源死算來求得一個滿意解。如果P=NP，那麼一方面計算所需要的資源大大降低了，另一方面就是解的精度更高了，機器智能無疑將大大提高。全面實現自學習、自進化就將成為現實，那麼最壞的情況就是：人類真得要考慮，所謂的機器人三原則是否只是個安慰劑了

N==1 || P==0

在《可能與不可能的邊界:P/NP問題趣事》一書的第二章，描述了一個P=NP的美好世界。

書中舉了幾個列子，羅列如下：

1. 解決NP問題的演算法可以用來尋找比自己更快的解決該問題的演算法（假設稱為厄巴納演算法），世界貿易組織在認識到該演算法的重大意義後，要求公開該演算法，供全人類

共同享用，相關各方將得到合理的補償，並成立專門委員會落實。

2. 厄巴納演算法幫人們戰勝了癌魔，治癒了艾滋病和糖尿病。可是，我們還不知道如何應對普通感冒。

3. 在演算法的幫助下，人類的天氣預測技術取得了不可思議的進步，可以提前一年準確預測溫度、風力、雲量和降水。類似的演算法可以做到準確預測風暴、龍捲風和颶風，讓人們有充足的準備和撤離時間。

新的預測工具料事如神，能提前告訴人們哪些球隊將進入9月份的冠軍爭奪賽。

新型電視允許人們直接下載三維渲染數據，然後控制虛擬的攝像機飛到賽場上的任意位置，隨心所欲地享受比賽過程。計算機在球棒擊球的那一瞬間，準確預測出球的飛行軌跡，然後立即選一個最佳的觀看角度，把比賽實時呈現出來。

蘭迪一邊喝著啤酒一邊啃著漢堡（飲料和食物變得更好吃了，因為厄巴納演算法改進了配方），一邊還欣賞著比賽。

原文：多看閱讀器

如果「P = NP」得到證明，意味著什麼？

具體參看果殼網 死理性派這篇文章。已經說的很白話了。

P vs. NP：從一則數學家謀殺案說起

具體參看果殼網死理性派這篇文章。已經說的很白話了。