第659章 哈密頓圖判定問題的多項式時間演算法

NP=P？」也稱「NP≠P還是NP=P」，被稱為世界級數學難題之一。

2000年5月，美國克雷數學研究所（CMI）在巴黎舉行的千年數學大會上宣布對攻克世界7個數學難題的懸賞，每個問題100萬美元獎金，「NP=P？」問題被列為7大難題之首。

7大難題中，目前只有「龐加萊猜想」被俄羅斯數學家佩雷爾曼證明（2002年），其他難題均懸而未決。

如果一個問題能在多項式時間內找到答案，我們稱之為「類P」或「P」問題。

對另一類問題，沒有已知的方法可以快速找到答案，但如果提供提供一個正確的答案，就能快速驗證，這類可以在多項式時間內驗證但是不確定能否在多項式時間內解決的稱為「NP」問題。

NP完全（NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中的決定性問題之一。

NP完全是NP與NP困難的交集，是NP中最難的決定性問題。

因此NP完全問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。

若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。

「NP=P？」問題可以簡單理解為：如果問題的正面答案可以很快驗證，其答案是否也可以很快計算？

「NP=P？」的答案將決定在多項式時間內驗證的問題是否也能在多項式時間內解決。

如果是P≠NP，那就意味著NP中存在比驗證更難的問題：它們不能在多項式時間內解決，但答案可以在多項式時間內驗證。

「NP=P？」的問題具有十分重要的意義，現代密碼學建立在NP≠P的假定之上，如果NP=P，從理論上說，密碼學會徹底崩潰。

哈密頓圖判定問題是NP完全的嗎？

根據姜教授自己的陳述，「因為哈密頓圖判定問題是NP完全問題，而任何NP完全問題有多項式時間演算法則有NP=P是普天下所有相關課本和著作的定理，所以哈密頓圖判定問題有多項式時間演算法等於說NP=P，如同一個人COVID-19測試陽性等於說他是新冠感染者一樣」。

哈密頓圖是一個無向圖，要求由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。在圖論中是指含有哈密頓迴路的圖，閉合的哈密頓路徑稱作哈密頓迴路（含有圖中所有頂點的路徑稱作哈密頓路徑）。

尋找哈密頓路徑是一個典型的NP-完全問題，所以大多認為通過哈密頓圖判定可以間接證明NP=P的問題。

為了減少刺激性，姜新文教授將摘要中「暗含NP=P」幾個字替換成「對證明NP=P有重要和積極意義」。

網友熱議：論文的可行性存疑，如果是真的將擊潰現有加密體系

論文發表后，引發了很多網友討論。

論文太短了，不可能證明這種難度的問題。

此前，曾有網友做了一些工作，認為這篇論文是偏「民科」的。他認為，姜新文教授此前沒有發表過任何權威的論文，而且這篇論文的長度太短了，對於這種難度的問題來說是完全不夠的。

當然這位網友也不是憑空猜測，他給出了自己的反例證明，感興趣的讀者可以參考文末原文鏈接。

另外，這篇論文的一個重要前提「MSP問題是一個NPC問題」，但是這個結論也不一定是對的。

親歷者：退休老教師只是想找個答案

曾親自上過姜老師課的網友表示，姜老師具備發表這篇論文的基本科學素養，計算複雜度知識和嚴謹邏輯推理能力。如果結論是錯的，希望有人能告訴他錯在哪，對於一個退休的老人，他只是求個答案。

至於論文中的maybe等詞，個人理解一是研究者的謙虛，二是確實也不能100%的保證證明沒問題。

如果NP=P問題得到解決，世界將會怎樣？

雖然沒有網友說的這麼誇張，但是NP=P如果得到證明，產生的影響還真挺大的。

到那時，我們常用的MD5加密演算法將會失效，判定一個串的MD5是否為給定值與尋找一個MD5等於給定值的串一樣輕鬆，RSA演算法也不再有效，尋找一個質因子和判斷整除性也變得一樣簡單。

事實上，基於類似原理的任何加密演算法都將成為一紙空談，計算機可以輕鬆根據密文推算出解密演算法（只要這個演算法是多項式的），互聯網將沒有任何安全性可言。

。