千禧年7大數學難題之一被中國人破解?國防科大教授發文稱證明NP=P

2020-11-22 騰訊網

新智元報導

來源：計算機科學等

編輯：白峰

【新智元導讀】近日，「計算機科學」刊發了一篇題為《哈密頓圖判定問題的多項式時間算法》，該文宣稱可以間接證明數學和計算機科學領域的NP=P難題。

論文刊發後，短短數天時間下載量就破千，但是關於這一證明的有效性，引發了

網友的熱議。

NP=P？為什麼這麼難

「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算法也不再有效，尋找一個質因子和判斷整除性也變得一樣簡單。

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

參考連結：

https://www.zhihu.com/question/29240825/answer/43662453

https://www.zhihu.com/question/411543712

http://www.matrix67.com/blog/archives/2552

http://blog.sina.com.cn/s/blog_54de27b80102yz41.html

相關焦點

  • 什麼是 P = NP 問題?
    看到這裡我們可能是一頭霧水，不由得發問：這四個問題也是我們由表及裡去理解P=NP問題的重要切入點，通過本文你將了解到包括但不限於以下內容：2 千禧年世紀難題時間鏡頭拉回2000年數學界出現了一個裡程碑事件：千禧年大獎難題千禧年大獎難題 Millennium Prize Problems 是七個由美國克雷數學研究所 Clay Mathematics
  • 我國數學家證明NP=P
    2020年7月出版的《計算機科學》(中國計算機學會會刊)發表了國防科技大學教授、湘潭大學計算機學院特聘教授姜新文題為《哈密頓圖判定問題的多項式時間算法》的論文,這標誌著在數學和計算機科學領域中最為重要的難題之一 "NP=P?"得到科學證明,論文刊出幾天後下載量近千次,引發有關學術群體熱議。
  • 世界七大數學難題之一 中國科學家破解龐加萊猜想
    據新華社北京6月3日電國際數學界關註上百年的重大難題——龐加萊猜想，近日被科學家完全破解。哈佛大學教授、著名數學家丘成桐3日在中國科學院晨興數學研究中心宣布，在美、俄等國科學家的工作基礎上，中山大學朱熹平教授和旅美數學家、清華大學兼職教授曹懷東已經徹底證明了這一猜想。
  • 中大教授朱熹平破解數學世紀難題龐加萊猜想
    中大教授朱熹平旅美數學家曹懷東破解龐加萊猜想該猜想為七大數學世紀難題之一據新華社電國際數學界關註上百年的重大難題———龐加萊猜想，近日被完全破解。哈佛大學教授、著名數學家、菲爾茲獎（即「國際傑出數學貢獻獎」，數學家最高獎項）得主丘成桐昨日在中國科學院晨興數學研究中心宣布，在美、俄等國科學家的工作基礎上，中山大學朱熹平教授和旅美數學家、清華大學兼職教授曹懷東已經徹底證明了這一猜想。100多年來，無數的數學家關注並致力於證實龐加萊猜想。20世紀80年代初，美國數學家瑟斯頓教授因得出了部分證明結果而獲得菲爾茲獎。
  • 中國科學家徹底證明龐加萊猜想破解百年數學難題
    新華社北京６月３日電（記者李斌）國際數學界關註上百年的重大難題－－龐加萊猜想，近日被科學家完全破解。哈佛大學教授、著名數學家、菲爾茲獎得主丘成桐３日在中國科學院晨興數學研究中心宣布，在美、俄等國科學家的工作基礎上，中山大學朱熹平教授和旅美數學家、清華大學兼職教授曹懷東已經徹底證明了這一猜想。
  • 請解開「P對NP」難題
    北京時間7月4日消息，「P對NP」問題一直是全球七大數學難題之一。
  • 千禧年大獎難題之始與未終
    略微遺憾的是，獎池通過投資逐年遞增的提議被克雷數學研究所的律師駁回了。受限於籌備時間的倉促，我們對獎池問題沒能進一步地協商，這就是七百萬美元大獎的由來。籌 備 千 禧 年 大 會在甄選難題和設置獎金的同時，另一項艱巨的任務是籌備將在巴黎召開的千禧年大會。孔涅教授作為法國方面的聯絡人，聯繫了法蘭西公學院作為大會的東道主。
  • 數學手抄報:千禧年大獎難題
    千禧年大獎難題(Millennium Prize Problems), 又稱世界七大數學難題， 是七個由美國克雷數學研究所(Clay Mathematics Institute,CMI) 於2000年5月24日公布的數學猜想。
  • 烏茲別克數學家聲稱解決千禧年大獎難題
    （原標題：烏茲別克數學家聲稱解決千禧年大獎難題）
  • 龐加萊猜想被證實 中國科學家破解百年數學難題
    中新網6月4日電 國際數學界關註上百年的重大難題——龐加萊猜想，近日被科學家完全破解。據新華網報導，哈佛大學教授、著名數學家、菲爾茲獎得主丘成桐3日在中國科學院晨興數學研究中心宣布，在美、俄等國科學家的工作基礎上，中山大學朱熹平教授和旅美數學家、清華大學兼職教授曹懷東已經徹底證明了這一猜想。
  • 中國破解百年數學難題 成就比哥德巴赫猜想重要
    據新華社電 國際數學界關註上百年的重大難題——龐加萊猜想，近日被科學家完全破解。哈佛大學教授、著名數學家、菲爾茲獎得主丘成桐3日在中國科學院晨興數學研究中心宣布，在美、俄等國科學家的工作基礎上，中山大學朱熹平教授和旅美數學家、清華大學兼職教授曹懷東已經徹底證明了這一猜想。
  • 世界7大數學難題之1被解?數學家稱能證明黎曼猜想
    在這之後的159年裡，數學界一直沒有停止對它的探索，但迄今並未獲得顯著進展。德國數學家戴維·希爾伯特在第二屆國際數學家大會上提出了20世紀數學家應當努力解決的23個數學問題，其中便包括黎曼假設。現今克雷數學研究所懸賞的世界七大數學難題中也包括黎曼假設。
  • 20年過去,千禧年數學七大難題仍有六題未解,唯一的解題者已隱退
    2000年5月，由美國富豪出資建立的克萊數學研究所，精心挑選了7大未解數學難題，無論你是數學家還是流浪漢，任何人只要解決其中一題，都可以領走100萬美金。美國希望通過懸賞的方式高效解決問題，對數學家而言，無疑也是一次揚名立萬的機會。這七道題也被稱為「千禧年數學七大難題」。
  • 數學天才張益唐,卻在美國刷碗7年,沉寂21年,58歲破解世界難題
    當時的張益唐一直想要攻克雅可比猜想，雅可比猜想是多變量多項式的一個著名問題，最初是由數學家雅可比於1939年提出，是代數幾何領域中最難攻克的難題之一，雅可比猜想之所以聞名，因為有很多試圖解決猜想的證明，都有藏於細節中的錯誤。但張益唐卻做到了，他僅用了兩年時間便完成了博士論文，並宣稱解決了雅可比猜想。
  • 最長數學證明破解世界難題:看完需要100億年
    上世紀80年代，美國數學家羅伯特-格拉漢姆懸賞100美元，請數學愛好者幫助他解決一個數學難題，這道數學難題困擾了格拉漢姆很長時間。三十多年來，一直未能有人拿出破解方案前來領賞。近日，一個由美英兩國三位數學家組成的研究團隊宣稱他們應該得到這筆獎金。
  • 159年的數學難題就這樣搞定了?並沒有
    有人稱他「數學媒人」阿蒂亞1929年4月22日出生於英國倫敦，今年89歲了。他是當今最偉大的數學家之一，背了一大堆榮譽，是英國皇家學會會長、愛丁堡皇家學會前會長、劍橋大學三一學院院長，曾被授予爵士封號。他是菲爾茲獎和阿貝爾獎的雙料得主。
  • 佩雷爾曼證明過程_佩雷爾曼龐加萊猜想證明pdf - CSDN
    月出版的《計算機科學》（中國計算機學會會刊）發表了國防科技大學教授、湘潭大學計算機學院特聘教授姜新文題為《哈密頓圖判定問題的多項式時間算法》的論文，這標誌著在數學和計算機科學領域中最為重要的難題之一 「NP=P？」
  • 中科大破解困擾數學界20多年的核心猜想
    近日，中科大教授在幾何學頂刊《微分幾何學雜誌》發文，這篇超過120頁的關於高維凱勒裡奇流收斂性的論文將對裡奇流的研究已經產生深遠的影響。被譽為數學諾貝爾獎的菲爾茲獎得主高度讚揚該研究成果是「幾何領域近年來的重大突破」！
  • 90後破解60年未解數學難題 因未過四級不能保研
    圖為：王驍威 　　名不見經傳的廣東韶關學院大四學生王驍威成功破解了國際數論學界的一個猜想但他偏科，英語沒過四級，還錯過了考研報名，想繼續研究數學的他如今面臨無學可上的尷尬。 　　鑽研4個月發現反例 　　成功推翻國際猜想 　　王驍威出生於1990年，是韶關學院數學系大四學生。
  • 俄羅斯天才數學家佩雷爾曼拒領百萬千禧年數學大獎
    這筆獎金本用來獎勵他解出數學界7大難題之一。 拒絕大獎 佩雷爾曼年過不惑，住在聖彼得堡一套公寓內。英國《每日郵報》3月23日報導，佩雷爾曼緊閉家門，在屋裡對門外採訪的記者說：「我應有盡有。」 100萬美元獎金由克萊數學研究所提供，獎勵佩雷爾曼證明數學界7大難題之一的「龐加萊猜想」。 克萊數學研究所所長詹姆斯·卡爾森在一份官方聲明中說：「格裡戈裡·佩雷爾曼解出了『龐加萊猜想』，從而為長達一個世紀的求解之路畫上句號。這是數學史上一個重要進展，將在長時間內為人所銘記。」