千禧年7大數學難題之一被中國人破解？國防科大教授發文稱證明NP=P
來源：計算機科學等
編輯：白峯
【新智元導讀】近日，「計算機科學」刊發了一篇題為《哈密頓圖判定問題的多項式時間算法》，該文宣稱可以間接證明數學和計算機科學領域的NP=P難題。
論文刊發後，短短數天時間下載量就破千，但是關於這一證明的有效性，引發了
網友的熱議。
NP=P？為什麼這麼難
「NP=P？」也稱「NP≠P還是NP=P」，被稱為世界級數學難題之一。
2000年5月，美國克雷數學研究所（CMI）在巴黎舉行的千年數學大會上宣佈對攻克世界7個數學難題的懸賞，每個問題100萬美元獎金，「NP=P？」問題被列為7大難題之首。
7大難題中，目前只有「龐加萊猜想」被俄羅斯數學家佩雷爾曼證明（2002年），其他難題均懸而未決。
對另一類問題，沒有已知的方法可以快速找到答案，但如果提供提供一個正確的答案，就能快速驗證，這類可以在多項式時間內驗證但是不確定能否在多項式時間內解決的稱為「NP」問題。
NP完全（NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中的決定性問題之一。NP完全是NP與NP困難的交集，是NP中最難的決定性問題。因此NP完全問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。
「NP=P？」問題可以簡單理解為：如果問題的正面答案可以很快驗證，其答案是否也可以很快計算？
「NP=P？」的問題具有十分重要的意義，現代密碼學建立在NP≠P的假定之上，如果NP=P，從理論上説，密碼學會徹底崩潰。
哈密頓圖判定問題是NP完全的嗎？
根據姜教授自己的陳述，「因為哈密頓圖判定問題是NP完全問題，而任何NP完全問題有多項式時間算法則有NP=P是普天下所有相關課本和著作的定理，所以哈密頓圖判定問題有多項式時間算法等於説NP=P，如同一個人COVID-19測試陽性等於説他是新冠感染者一樣」。
哈密頓圖是一個無向圖，要求由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。在圖論中是指含有哈密頓迴路的圖，閉合的哈密頓路徑稱作哈密頓迴路（含有圖中所有頂點的路徑稱作哈密頓路徑）。
尋找哈密頓路徑是一個典型的NP-完全問題，所以大多認為通過哈密頓圖判定可以間接證明NP=P的問題。
為了減少刺激性，姜新文教授將摘要中「暗含NP=P」幾個字替換成「對證明NP=P有重要和積極意義」。
網友熱議：論文的可行性存疑，如果是真的將擊潰現有加密體系
論文發表後，引發了很多網友討論。
論文太短了，不可能證明這種難度的問題。
此前，曾有網友做了一些工作，認為這篇論文是偏「民科」的。他認為，姜新文教授此前沒有發表過任何權威的論文，而且這篇論文的長度太短了，對於這種難度的問題來説是完全不夠的。
親歷者：退休老教師只是想找個答案
曾親自上過姜老師課的網友表示，姜老師具備發表這篇論文的基本科學素養，計算複雜度知識和嚴謹邏輯推理能力。如果結論是錯的，希望有人能告訴他錯在哪，對於一個退休的老人，他只是求個答案。
至於論文中的maybe等詞，個人理解一是研究者的謙虛，二是確實也不能100%的保證證明沒問題。
如果NP=P問題得到解決，世界將會怎樣？
雖然沒有網友説的這麼誇張，但是NP=P如果得到證明，產生的影響還真挺大的。
到那時，我們常用的MD5加密算法將會失效，判定一個串的MD5是否為給定值與尋找一個MD5等於給定值的串一樣輕鬆，RSA算法也不再有效，尋找一個質因子和判斷整除性也變得一樣簡單。
事實上，基於類似原理的任何加密算法都將成為一紙空談，計算機可以輕鬆根據密文推算出解密算法（只要這個算法是多項式的），互聯網將沒有任何安全性可言。
參考鏈接：
https://www.zhihu.com/question/29240825/answer/43662453
https://www.zhihu.com/question/411543712
https://www.matrix67.com/blog/archives/2552
https://blog.sina.com.cn/s/blog_54de27b80102yz41.html