佩雷爾曼證明過程_佩雷爾曼龐加萊猜想證明pdf - CSDN

2020年7月出版的《計算機科學》（中國計算機學會會刊）發表了國防科技大學教授、湘潭大學計算機學院特聘教授姜新文題為《哈密頓圖判定問題的多項式時間算法》的論文，這標誌著在數學和計算機科學領域中最為重要的難題之一 「NP=P？」得到科學證明，論文刊出幾天後下載量近千次，引發有關學術群體熱議。

>>>>

本文僅作為學術分享，如有侵權，刪文處理

如何看待科學網發布文章稱「我國數學家證明 NP=P」，是真的嗎？如果是，會帶來怎樣的影響?

- 知乎https://www.zhihu.com/question/411543712

「NP=P？」也稱"NP≠P還是NP=P」，實質是P對NP關係問題，被稱為世界級數學難題之一。2000年5月，美國克雷數學研究所（CMI）在巴黎舉行的千年數學大會上宣布對攻克世界7個數學難題的懸賞。P對NP關係問題被列為新千年7大難題之首。

2005年《科學》雜誌將"NP=P？」問題作為數學科學的代表，列為25個學科難題之一。2018年《科學》雜誌再次列出125個亟待解決的科學難題，其中第19個問題就包含"NP=P？」問題。迄今為止，新千年7大數學難題中除了俄羅斯數學家佩雷爾曼2002年證明了有關拓撲學的「龐加萊猜想」之外，其他難題均懸而未決。

據介紹，20世紀，現代計算機問世，NP與P的關係問題就成為計算機科學和數學交叉領域的基礎科學問題。通常，算法求解一個問題需要耗費時間，這被稱為算法的時間複雜度。求解同一個問題的不同算法耗費的時間可能不同，只有採用多項式時間算法才能最有效解決問題。NP≠P，其核心是否定不同選擇方法，認為有些問題不存在多項式算法。而姜新文證明了「NP=P」，表明多項式算法實際上是存在的。

姜新文從1986年開始講授《算法設計與分析》課程，結合此前學習圖論時關於哈密頓圖判定問題的思考，開始研究P對NP關係問題。9年之後，姜新文於1995年發表了研究成果《簡單無向圖H性質判定》，開始思考運用整體觀思路來處理一個有限系統的計算問題。

他首先建立了一套基於數學歸納法的證明框架，然後堅持探索滿足這套證明框架的算法設計。從1995年開始之後的15年中，經歷了2000次以上設計、修改與調整，到2010年底得到預期效果。姜新文35年的潛心探索，終於獲得成功！

「NP=P」得到證明具有重要的科學意義與應用價值。因為這將為計算機科學領域帶來截然不同的理論極限和發展前景。在現代經濟社會中，大量科研、生產、國防與社會服務過程都需要採用正確的快速計算方法。可以期待，在「NP=P時代」，地球科學、生命科學、宇宙科學、環境科學、生物科技、材料工程、管理科學、數學科學、物理科學等多個學科的研究都將得到更深入的推進。

此外，由於現代密碼學是建立在NP≠P的假定之上，而現在NP=P得到證明，對密碼學的發展是一次巨大的科學挑戰。

相關論文信息：doi: 10.11896/jsjkx.191200176

本公眾號回覆：NP，即可獲取論文全文

作者@ 留德華叫獸的回答

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

NP完全問題(NP-C問題) 

即NP是否等於NP 

是世界七大數學難題之一   

作為運籌學|組合優化的博士 ，碩士對這個問題證明的某種特殊情況做出過一丁點微小的貢獻（待我娓娓道來：）。博士研究組合優化問題（NP難）的整數規劃建模和精確算法  並且在德國博士答辯的口試題之一就是關於NP問題的 ，覺得有必要用最通俗的語言先為大家科普一下   

1. 什麼叫P 和 NP問題   

首先這是一個算法複雜度的概念  P問題：多項式時間「可解」的"簡單"問題  NP問題：給一個解，多項式時間可以判定該解是否「正確」  NP完全問題：可以被所有NP問題多項式時間「轉化」到的"最難"的一類問題  （目前比較「通用」的有21個該問題）

以上打引號地數學上不是很精確，目的是讓大家更好地get point，下圖很好地刻畫了P和NP的關係

2. NP難有多難

大家應該都聽說過指數爆炸吧？  雖然還未能證明P是否等於NP，但是學術界「普遍」認為它們不等。因此 ，求解一個一般的NP難問題的精確解（全局最優解），它的算法複雜度通常是指數級的 。

什麼意思呢？  算法複雜度是浮點運算數相對於變量n的一個關係。假設該指數的底是2  即：算法複雜度是O(2^n) ，也就是說 ，如果當變量n=100的時候 ，運算時間是10秒鐘，那麼當變量n=101的時候，運算時間「最壞情況」是20秒鐘(直接翻倍)  。當n=102 ，運算時間最壞 40秒(四倍)  。當n=110，運算時間最壞是 10240秒=2.844小時！！！  (多了10個變量，運算時間是2的10次方倍)   

3. 退而求其次-近似算法、啟發式算法

既然要求得全局最優解是指數級算法複雜度的 ，工業界可沒有這個耐心等這麼久 ，（例如：網約車的實時派單、導航軟體計算最短的k條路線），於是有了近似算法和啟發式算法 。

近似算法是指雖然我求不到全局最優解， 但是我設計一種算法，用數學證明該算法得到的解在全局最優解的1/k-k倍以內 。並且該算法通常是多項式的--快。

啟發式算法（如：貪婪算法），設計一種快速的多項式時間算法，求得一個正確的解  但是不知道這個解的質量（離全局最優解有多遠）

具體請見：https://zhuanlan.zhihu.com/p/30140008  

4. 回到正題：如何證明NP=P及碩士期間做過的微小工作 

只要證明21個NPC問題中的任何一個  

是多項式時間可解的， 即證明了NP=P，例如經典的背包問題（Knapsack problem） 

定義：  我們有 n 種物品，物品 j 的重量為wj，價格為pj。我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W。如果限定每種物品只能選擇0個或1個，則問題稱為0-1背包問題。

https://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98

我在美國Clemson讀研期間的碩士論文，證明了一種特殊的背包問題是多項式時間可解的 ，有多特殊呢？  

上式中目標函數的係數p必須滿足 ：

可以簡單地理解為：係數p呈指數級上升 

當係數滿足這個條件的時候，我們證明了這個整數規劃的係數矩陣是Total Unimodular的 ，即這個整數規劃問題等價於它的線性規劃鬆弛，因此這類背包問題是多項式時間可解的  。這大概是我這個數學博士在學術上最高光的時刻， 從此一路走下坡，越做越應用 ，甚至轉行到了令數學同行所不齒的人工智慧。

書歸正傳  文章最後發表在了JOGO上面  感興趣的小夥伴可以下載預印版  

http://www.optimization-online.org/DB_FILE/2015/12/5246.pdf  www.optimization-online.org   

從這個意義上講  我是不是也對證明P等於NP？做出了一丁點微小的貢獻呢？  笑～逃～   

5. 假設P=NP

世界會怎樣？世界將一片美好 。卡普的21個NP完全問題將是多項式時間可解的 

工業界諸多實際的組合優化問題將會變得簡單 ，任何密碼將會在「短時間」內被攻破。整數規劃、01規劃、背包問題全部獲解，運籌學將登上一個全新的高度；資料庫的串行化、多處理器調度等問題也隨之解決，大大提高了計算機的性能。詳見：  

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

以及， 我們這些研究大規模組合優化、離散優化精確解的小夥伴都要失業了？  因為它們變成了很「簡單」的問題了  還用得著我們去研究麼  哈哈  

簡單點評:  

在被國際最權威的數學|理論計算機雜誌  同行評審、刊登出來之前  這個千禧年大獎難題哪有這麼容易攻破  (  @Yuhang Liu  提到:國際審稿都給了拒稿)  更何況發表這篇文章的  是一本既不是SCI也非EI的中文「學術」雜誌。因此也就沒有花時間去「找茬」，但我還是很欽佩老教授退休了還繼續啃硬骨頭的鑽研精神，也很佩服《計算機科學》這本雜誌。不管怎麼說，都是一次歷時七年以上、有意義的嘗試，而非我這種知乎答題者花了3小時寫的「民科」。

我這篇科普文，有不專業的地方， 還請專業人士指正 。

最後，在查看其他回答的時候 ，發現  @G.Cui  的回答更完整地科普了什麼叫P和NP。

作者@ G.Cui的回答

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

更新：科學網的原文似乎已撤下。

實際上對相關內容一點也不了解的人很可能會低估這個問題的難度，有的答主不具體指出錯誤會讓一些旁觀者感到不滿，這也可以理解，但是其他答主也不能走向另一個極端，更有甚者用民族主義綁架數學、科學，我認為嘲諷攻擊何時也不應該有。

簡單來說，論文證明的方向——「證明一個NPC問題是P的」是對的，也就是說，如果論文的所有細節正確，則 P=NP 。論文本身的正確性尚未討論出公認結果，媒體給的報導如果認為是「假定論文正確，則P=NP 」則基本正確，無條件嘲諷沒有必要，但是報導中還是有些科普細節不當。

我並沒有水平評價論文內算法的正確性，我只是想對報導中其他的錯誤進行評論。因為問題是「如何看待科學網的文章」，我想我對報導的評論並不屬於無關內容，請輕噴。

對論文本身的評價參見高贊，下面我只對科學網的報導中的問題說幾句——

報導裡：

NP≠P，其核心是否定不同選擇方法，認為有些問題不存在多項式算法。而姜新文證明了「NP=P」，表明多項式算法實際上是存在的。

這根本就沒理解P v.s. NP 問題是啥意思，

1.「有些問題不存在多項式算法」，等價的說法應該是「存在一些 問題 不是 P 問題」，也就是說，不是所有問題都是 P 的；

2.P≠NP 等價的說法應該是「存在一些NP問題不是P問題」。

前者與 P v.s. NP 毫無關係，因為早就知道有的問題不存在多項式算法（比如 HALT 都不是可判定的），報導把這二者混為一談，絕口不提 NP 問題是什麼，這是不對的。

姜的文章就是試圖做最後一條，他論文的方向在說某個問題是NPC的，然後給了一個多項式算法，所以證明 P=NP。證明大方向沒錯，但這些步驟的細節估計（我沒能力給出確定的回答，但我的直覺是 P≠NP）是有問題的。

參考

1.^Wikipedia. P. https://zh.wikipedia.org/wiki/P_(複雜度)

2.^Wikipedia. NP. https://zh.wikipedia.org/wiki/NP_(複雜度)

3.^Wikipedia. NPC. https://zh.wikipedia.org/wiki/NP完全

4.^https://zh.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg

作者@ Climber.pI 的回答 

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

Gerhard J Woeginger 在去 RWTH Aachen 之前, 曾經維護了一個關於 P 和 NP 關係的各種偽證的頁面 (一直更新到了 2016 年): 

P-versus-NP page  www.win.tue.nl

通過簡單的搜索不難發現第 53 條如下:  53. [Equal]:In April 2009, Xinwen Jiang published a proof for P is equal to NP. He provided an algorithm for the Hamilton circuit problem, and states"It seems our algorithm is a polynomial one".The paper can be found athttp://xinwenjiang.googlepages.com/. An earlier version of his paper was published in a Chinese journal in 2007. Further versions have been published in 2010 and 2011. More information on the current version of the proof is available athttp://trytoprovenpvsp.blog.sohu.com/entry/. Since May 2013, the paper"A Polynomial Time Algorithm for the Hamilton Circuit Problem"is available athttp://arxiv.org/abs/1305.5976. (Thanks to Maris Ozols for providing some of these links.)

有興趣查證各種連結的同學, 可以結合 https://archive.org/web/ 來考證相關的歷史連結.

我也不是很理解為什麼要討論這種 not even wrong 的東西. 但是很迷的是, 看樓下的博客連結, 這一系列結果竟然還拿到了 NSFC 的資助? 比起直接證明 P 和 NP 的關係, 建議考慮證明或推翻以下較為容易的問題:

● 證明 P 不等於 PSPACE;

● 給出 Learning with Error 問題的經典或量子多項式時間算法;

● 證明 AM=MA, 如果覺得太容易的話, 可以考慮證明 P=BPP;

● 證明 QCMA = QMA, 或 QCMA = QMA(2), 或者裡面隨便挑兩個證明相等;

● 證明 NL=L 或 BPL=L;

● 證明 BQP=QPIP.

哦忘記說了, 第二項是 P=NP 的推論. 因為 LWE 的 hardness 證明依賴的 poly-approximated GapSVP 是在 NP cap coNP 裡的, 所以能導出 LWE 的經典多項式時間算法. 作為腳註, Regev 曾在某次報告中表示, 「每年都有幾天, 我早上醒來, 會收到郵件聲稱給出了某些 lattice problems 的多項式時間的算法」. 如果有人能給出 LWE 的 (量子) 多項式時間算法的話, 我會非常高興, 因為我個人很不喜歡現在 LWE-based quantum delegation 的這些結果. 

最容易證明的可能是第五項, 今年 STOC 的 workshop 上有幾個大佬表示基於近年的一系列進展, 有望在十年內證明 BPL=L -- 目前最好的上界是二十多年前 Saks-Zhou 的 BPL is in L^{3/2}. 剩下最容易的可能是第三項, 但是現在甚至沒有比 P=BPP 更弱的備選前提條件. 第四項和第六項目前沒有任何頭緒, 第六項也有一些人認為不成立.

作者@  Manchery 的回答 

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

不認可在該問題下用媒體誇大其詞這一人民群眾喜聞樂見的現象而掩飾了問題本質的一切回答，包括最高贊。

首先給出我認知中的一個事實：

判定哈密頓圖是一個 NPC 問題；找到了任何一個 NPC 問題的多項式算法，就能夠得出 P=NP 的結論（從這一結果得到 P=NP 的這一過程非常簡單，就像證明了三邊相等，則兩個三角形相似一樣簡單，因此足以略過不提）。

按照上面的事實，「如果這位老師的證明是正確的，那麼他確實就是證明了 P=NP」。這一說法是沒有問題的，包括這位老師自己也就是這麼認為的，比如他自己寫到：

《哈密頓圖判定問題的多項式時間算法》發表_XinwenJiang_新浪博客：

https://link.zhihu.com/?target=http%3A//blog.sina.com.cn/s/blog_54de27b80102yz41.html

《哈密頓圖判定問題的多項式時間算法》發表在2020年第7期的《計算機科學》。因為哈密頓圖判定問題是NP完全問題，而任何NP完全問題有多項式時間算法則有NP=P是普天下所有相關課本和著作的定理，所以哈密頓圖判定問題有多項式時間算法等於說NP=P，如同一個人COVID-19測試陽性等於說他是新冠感染者一樣。雖然最終按照建議和希望，將摘要中「暗含NP=P」幾個字替換成「對證明NP=P有重要和積極意義」，以減少刺激性，但這句話本來可以整體不說。陳景潤發表在《科學通報》的、關於求證哥德巴赫猜想的巔峰之作，也只是命名《表達偶數為一個素數及一個不超過兩個素數的乘積之和》。感謝所有相關的人的辛勤工作。2020年發生的世界性疫情沒有阻擋我們的科學攀登。這一次，扎紮實實做研究，把論文寫在中國大地上的要求，給了所有的人奮勇前進的無窮力量。當人們傳頌國外數學家因為疫情宅在家裡解決數學難題的時候，同樣宅在家裡的他們的中國同行，也同樣在做著艱苦的努力。

以及他的掛在arxiv上的論文的摘要也寫到：

Our result implies NP=P

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

因此，只能說媒體並不具備鑑別這一論文真偽的能力（這是十分常見的），但我們並不能說媒體誇大其詞了。我更相信媒體聽到的就是「我們證明了P=NP」（僅是我個人相信）。

我認為對這個問題的關注點更應該放在這個證明對不對，如果不對，他為什麼發表了，如果對，為什麼沒有得到國際學術界的認可。更應該把這一問題類比成 望月新一在日本宣布了自己證明了ABC猜想但遭受了質疑，而不是類比為一次媒體誇張報導的事故（當然媒體未經嚴謹求證的報導也是一個問題，但這不同於誇張報導）。

關於這一證明對不對，也有很好的回答，以及該回答最下面也有 關於P、NP等的背景知識 可供參考：

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

另一個解釋了 P 和 NP 是什麼的回答（他意在指出即使這篇報導的主要內容在證明正確這一前提下是沒有問題的，但其中對於背景知識的科普依然是有瑕疵的）

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

另一高贊回答提到了這位老師的這一證明已經被人收錄在錯誤證明裡面了（但我並沒有能力辨別這一證明的真偽，我在這裡也並不是為了強調他是錯的或對的）

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

編輯 ∑Gemini

來源：運籌OR帷幄

文章推薦

☞最全數學各個分支簡介

☞十大中國數學之最

☞數學和編程

☞機器學習中需要了解的 5 種採樣方法

☞北大讀博手記：怎樣完成自己的博士生涯？非常具有指導性！

☞施一公：為什麼要獨立思考、為什麼要尊重科學？