世界級難題
等待一個結論
8月2日，科學網發布了一篇文章，標題是《我國數學家證明NP=P》。
超模君看到這個標題時，不敢相信啊！如果是真的，姜新文教授相當於是下一個「圖靈獎」得主。
NP=P?
「NP=P？」也稱「NP≠P還是NP=P」,它的實質是P對NP關係問題，被稱為世界級數學難題之一。
假設你參加一個盛大的宴會，想要知道裡面有沒有認識的人。宴會的主人對你說，你一定認識正站在甜點桌右邊角落裡的女士小龍女。你立刻掃向那裡，發現他說的是對的。而如果他不告訴你這些，你就需要環顧整個大廳，審視過每一個人，然後才知道有沒有認識的人。宴會主人的暗示，容易找到這一步就是P，你按照他的提示發現自己認識小龍女，容易檢查這一步就是NP。
這其實就是：生成問題的一個解，通常比驗證一個給定的解，要花費更多時間。比如，如果讓你計算世界上所有原子個數的總和，這個問題很困難，甚至無解。但是，如果有人告訴你世界上一共有500個原子，那麼你能很快驗證他是錯的。很容易驗證，卻不容易求解，這種就是NP類問題。
P類問題是可以在多項式時間內解決並驗證的一類問題；NP類問題是可以多項式時間驗證但是不確定能否在多項式時間內解決的一類問題。
顯然，所有P類問題都屬於NP類問題，但是無法確定NP是否等於P。
至於引文中所提到的「多項式時間」，我們可以這樣理解，多項式表達如下圖：
如果要用計算機解開一個多項式，計算機是不知道這個問題難不難的，它只會拆解成非常多的步驟去執行。計算機如果覺得這個問題難，它就會花費更多的時間，時間越長就意味著問題越難，這個時間就是多項式時間。
多項式時間和非多項式時間消耗曲線對比圖
也就是說，如果NP類問題無法在多項式時間內解決，那麼依照當前的計算能力基本上是無解的。所以，如果NP類問題能在多項式時間內解決，也就是NP=P,它所產生的意義不可估量。
2000年初美國克雷數學研究所的科學顧問委員選定了7個數學難題，每個難題的解決有百萬美元獎金，「NP=P?」正是新千年7大難題之首。
1、NP=P？2、霍奇猜想3、龐加萊猜想4、黎曼猜想5、楊—米爾斯存在性與質量間隙6、納維—斯託克斯存在性與光滑性7、BSD猜想
此外，《Science》更是在2005年和2018年，將「NP=P？」列為數學科學的代表難題之一。
可怕的是，一旦「NP=P」被證明，那麼基於假定「NP≠P」的學科將崩潰，比如現代密碼學。而如果這個「證明」被證明是真的，舉一個通俗易懂的例子：驗證碼將變得毫無意義。
事實上，科學網的這篇文章一出來，迎來的不是誇讚，而是懷疑。「NP=P?」這個問題是否被解決，它需要世界上的頂級數學家們進行驗證，而不是憑藉著某一個雜誌的版面給予不確定性報導。
目前科學網的這篇文章已經被刪除，但也沒人證明姜教授錯了。
那到底證明了嗎？
有意思的是，雖然科學網的報導遭到大量懷疑，但姜新文教授的論文—《哈密頓圖判定問題的多項式時間算法》，至今還沒有被發現重要錯誤，但是也沒有人站出來說他對。
其實，早在2010年，姜新文教授就已經推出了一篇長達32頁的文章。這篇論文在arXiv上掛了7年，十年過去，文章刪刪減減，收錄到知網只剩20頁，最後在2020年7月發表在不是SCI的《計算機科學》雜誌上。
這也是姜教授被質疑的原因之一，倘若真是具有可信性和科學性的論文，為什麼至今沒有得到國際學術界的認可？
另外，在這篇文章中一開始用到了12個參考文獻，其中10篇都是姜新文教授自己的，不知是有意還是無意，文章中略去了其他人的名字，明顯不符合學術規範。
上圖為原版論文，知網新版論文有20個參考文獻，6個來自於他自己
而且，他在大學從事研教三十年，可他大部分論文都發表在一本名為《計算技術與自動化》的雜誌上，我們可以看一下這個雜誌的影響因子。
從業至今，姜教授沒有發表過一篇具有影響力的論文，突然說自己解決了一個世界級數學難題。而他的這篇論文十年間沒有被任何一個有影響力的期刊接收，姜新文教授被質疑，似乎也在情理之中。
我們再來看姜教授的這篇論文—《哈密頓圖判定問題的多項式時間算法》。
1859年，數學家哈密頓（Hamilton）提出了一個叫做「週遊世界」的遊戲。在一個正十二面體的20個頂點上，一次標註了倫敦、巴黎、莫斯科等世界上著名的大城市。要求遊戲者從某個城市出發，把所有的城市都走一次，且只能走一次，然後回到出發點。
在圖論中，走過途中每個頂點一次且僅一次的路線稱為哈密頓路徑，走過途中每個頂點一次且僅一次的迴路稱為哈密頓迴路，具有哈密頓迴路的圖叫做哈密爾頓圖。
根據姜教授自己的講述：
「因為哈密頓圖判定問題是NP完全問題，而任何NP完全問題有多項式時間算法，則有NP=P是普天下所有相關課本和著作的定理，所以哈密頓圖判定問題有多項式時間算法等於說NP=P，如同一個人COVID-19測試陽性等於說他是新冠感染者一樣。」
1、NP完全問題（NPC），Nondeterminism Polynomial complete，存在一個NP問題，所有的NP問題都可以約化它，只要解決了這個問題，那麼NP問題就解決了。需要滿足2個條件：它首先是一個NP問題；所有的NP問題都可以約化到它。2、NP難問題，NP-hard，它滿足NPC問題定義的第二條但不一定滿足第一條，即所有的NP問題都能約化到它，但是不一定是一個NP問題。
它們四個的關係可以用下圖表示：
即判定哈密頓圖是一個NPC問題，找到了任何一個NPC問題的多項式算法，就能夠得出P=NP的結論。
換句大白話就是：條條大路通羅馬，找到任何一條能通往羅馬的路，那麼就可以說NP=P。
姜教授認為他這樣證明是沒有問題的，十年來，也一直在等人給他一個結論。
激烈的討論
「NP=P？」的分量非常重，這麼多年沒有得出一個結果，不是因為沒有人研究，而是真的好難。
2010年8月6日，惠普實驗室的vinay deolalikar教授宣布證明了P≠NP，證明論文多達100頁。
vinay deolalikar教授郵件內容
deolalikar教授把他的證明過程放在自己的博客主頁上，8月8日，計算機科學家Lipton在博客上討論了這篇論文，評價道：
「這是一個值得認真對待的證明」。
事情發生後，引來了大量學術性的評論，很多都是同行，看法各有不同。
8月9號，Lipton在參考了大家的評論後，又重新寫了一篇新的評論，指出了deolalikar論文中的一些漏洞。
因為在這篇文章下面有大量有價值的評論，猶他大學計算機學院教授Venkatasubramanian建立了一個可以被用戶編輯的谷歌文檔，這些評論都被整理在其中。
8月10號，在陶哲軒的幫助下，這個文檔被轉換成一個WIKI架構的頁面。
Lipton的文章下面成了大家的討論平臺，許多學術性的批評出現，有更多的科學家參與到博客的討論和WIKI頁面的編輯。deolalikar教授也在各方質疑下不斷更新自己的論文。
這場討論推進了deolalikar教授改進自己的證明，也促進了公眾對NP=P?問題的了解。Lipton和陶哲軒認為這場在網際網路平臺上的討論產生了良好效果。
8 月 12 日，Lipton公布出了一封來自美國理論計算機科學家尼爾.伊莫曼（ Neil Immerman ）的信，指出了兩個此前未被認真討論的漏洞。
8 月 13 日，Deolalikar 貼出了一篇關於自己的證明的解釋性文檔。
8 月 14 日，在很多科學家的共同討論中，人們逐漸釐清 Deolalikar 的論文的根本問題在於把兩個沒有在論文中被嚴格定義出來的直觀概念混淆在一起，從而做出了不完善的論證。
8 月 15 日，Lipton 貼出了他對於一周以來討論的總結。
人們關於論文已經基本上認為證明不能成立，當然也可能多數人都犯了錯，關於「NP=P?」問題的討論至今仍在繼續。
相較於vinay deolalikar教授長達100頁的論文，姜教授的論文實在是太短了。
另外，在姜教授的這篇論文中，我們可以看到，他的結束語是「結果可能對於證明NP=P有重要意義」，和他5年前在自己博客中的說辭已經發生了變化。
上圖來自新版論文截圖
上圖為2015年姜教授的博客內容截圖
「NP=P？」問題的重要性不言而喻，就連陶哲軒大神也對它十分關注。這也就是為什麼消息一出來，國內各大新聞網站就把它推上了首頁，引起了大家的廣泛質疑，因為所有人都想見證這歷史性的一刻。
而即使這次「NP=P」被證明是錯的，也都將會是中國數學史上一次偉大而又不可磨滅的大事件。
參考文獻：
姜新文.哈密頓圖判定問題的多項式時間算法[J].計算機科學,2020,47(07):8-20.
作者簡介：超模君，數學教育與生活自媒體博主，新晉理工科奶爸。出版過《芥子須彌 · 大科學家的小故事》；《數學之旅·閃耀人類的54個數學家》。後續數學文化創意多多，歡迎關注認識！