如何評價波恩大學 Norbert Blum 關於 P≠NP 的證明？

01-12

文章見： [1708.03486] A Solution of the P versus NP Problem
能不能解釋一下證明的過程與爭論的焦點呢？

目前學界對此較為謹慎，需要等待同行的審查和評定。

題主在問題描述中寫道：

能不能解釋一下證明的過程與爭論的焦點呢？

恐怕這有點困難，因為如果讀者不是長期研究這個領域，三言兩語難以闡述清楚。若是大家真的有興趣，可以參考文末的幾個鏈接。

想瀏覽最新進展的話，大家可以跟進 Stack Exchange 上的這個問題，有人在持續更新。

( 08.17 更新：Stack Exchange 上的這個問題從 " Where is Norbert Blum"s 2017 proof that P≠NP being discussed? " 修改成了 " Is Norbert Blum"s 2017 proof that P≠NP correct? "）

@月光寒提到了 Luca Trevisan 的博文和動態，我這裡就不再贅述，如果討論有後續更新，大家請移步他的回答。

@WWK 提到了 Scott Aaronson 的博文，Scott 也對「新證明」持保守態度，並且打賭20萬美金這個「新證明」站不住腳。

似乎不少人邀請了 @王希來回答，他表示已經關注了該問題並且正在讀。大家不要催他，因為這個證明有38頁……略蛋疼，誰讀誰知道。

更多的參考鏈接見文末。

我比較認同 Alon Amit 的這段話（他是 Quora 上數學話題的優秀答主，有 54k 關注者）：

我覺得這篇論文經不起推敲。諸如 P≠NP 這樣深刻的定理，已經經過了大量的研究，有很大可能需要更加深遠的新方法才能解決。通過略微加強已知和現有的方法來解決這個問題，不是不可能，只是可能性非常非常非常低。

原文如下：

I don』t think this paper will stand up to scrutiny. A profound theorem which has been as massively researched as as P≠NP will, in all likelihood, be solved with deep and far-reaching new techniques. It』s not impossible that it will be solved with a slight enhancement of known, existing methods, but it』s just very, very, very unlikely.

這段話是他在8月14號寫的，他在回答中也一再說明這僅僅是個人觀點。

一些較為正式的參考鏈接：

Norbert Blum 在 arXiv 上的原文：

[1708.03486] A Solution of the P versus NP Problem
（PDF 格式）A Solution of the P versus NP Problem

Quora 上的討論：

What』s the status of Norbert Blum』s claim that P≠NP ?

Stack Exchange 上的討論：

Is Norbert Blum』s 2017 proof that P≠NP correct ?

Luca Trevisan 的博文：

On Norbert Blum』s claimed proof that P does not equal NP

Scott Aaronson 的博文：

What I believe II (ft. Sarah Constantin and Stacey Jeffery)

John Baez 的博文：

Norbert Blum on P versus NP

Luca Trevisan已經指出了一個錯誤：

Andreev"s function, which is claimed to have superpolynomial circuit complexity (abstract, then section 7), is just univariate polynomial interpolation in a finite field, which, if I am not missing something, is solvable by Gaussian elimination.

看起來是不會有大新聞了。

Update:

Luca現在說他之前想錯了：

You are right, guys, I misunderstood the definition of Andreev"s function: it"s not clear that it reduces to polynomial interpolation.

所以看起來事情還沒有定論

更新一下：

Stackexchange幾個小時前有了一個最新答案 https://cstheory.stackexchange.com/a/38832

I am familiar with Alexander Razborov whose previous work is extremely crucial and serves as a foundation for Blum"s proof. I had the good luck of meeting him today and wasted no time in asking for his opinion on this whole matter, on whether he had even seen the proof or not and what are his thoughts about it if he did.
To my surprise, he replied that he indeed was aware of Blum"s paper but didn"t care to read it initially. But as more fame was given to it, he did get a chance to read it and detected a flaw immediately: namely that the reasonings given by Berg and Ulfberg hold perfectly for the function of Tardos, and since this is so, Blum』s proof is necessarily incorrect as it contradicts the nucleus of the sixth theorem in his paper.

看這樣子是基本可以確定證明是錯的了。

-------------------------------------------------------------------------

Stackexchange上有討論：

Where is Norbert Blumamp;#x27;s 2017 proof that $P
e NP$ being discussed?

看起來Theoerm 5貌似沒啥問題，問題可能在Theorem 6

大牛Scott Aaronson表示：

To everyone who keeps asking me about the 「new」 P≠NP proof: I』d again bet $200,000 that the paper won』t stand, except that the last time

I tried that, it didn』t achieve its purpose, which was to get people to
stop asking me about it. So: please stop asking, and if the thing
hasn』t been refuted by the end of the week, you can come back and tell
me I was a closed-minded fool.

要是一周內沒發現問題歡迎去打臉

What I believe II (ft. Sarah Constantin and Stacey Jeffery)

數學不同方向隔行如隔山，吃瓜群眾只能表示圍觀。

搬運一個4chan /sci/ 的評論

/sci/ - https://arxiv.org/abs/1708.03486 I realize there a - Science amp;amp; Math - 4chan

He has a few papers on data structure lower bounds and a paper on his pet model of Boolean network functions published in a low-impact journal. He is not a reputable researcher on the topic, and the paper makes a bizarre claim that a lower bound method for monotone circuits extends easily to general boolean circuits. I don"t, for example, see how Theorem 6 couldn"t be applied to the majority function to extend the known Ω(n2) lower bound for monotone circuits to general circuits, contradicting the known O(log n) constructions for computing majority with general circuits.

About a year ago, there was a similar submission: https://arxiv.org/abs/1602.04781 which also claims P!=NP (in different words). If you look at the end of the paper, the author thanks Norbert Blum for reviewing (and indeed google confirms they are both professors at the University of Bonn). Not to say that Professor Blum"s submission is invalid, but it certainly hurts credibility in my mind.
It"s also worth noting that Blum"s paper has some of the original criticisms I had of Hauptmann"s, namely that it doesn"t seem to connect to existing research on the topic, such as why this approach succeeded where others failed or how this approach relates to the massive amount of open questions that are closely tied to the P vs NP problem.
To be specific, the paper I linked claims that the Polynomial Hierarchy does not collapse all the way, but a well known result is that if P = NP then PH collapses entirely, therefore making any claims to the contrary is also making a claim against P vs NP.

對待科學研究問題，激動，情緒化，投票和站隊都沒用，理性和真理是客觀的，是不以人的意志為轉移的。

雖然有一些大牛都表示懷疑，那只是猜測而已。論文作者不是逗逼，不是民科，是受過科班訓練的研究人員。論文作者把這篇論文放到arxiv上之前，自己心裡很清楚P vs NP這個經典問題的份量: 如果不出意外，會是什麼樣的驚天突破！因此，他不可能不再三審慎地檢查自己的論文。

這個時候，大家應該平心靜氣地去仔細讀他的論文，檢查他的邏輯是不是有漏洞。我認為，如果有漏洞，這樣的邏輯漏洞也不會太明顯，否則作者自己能檢查出來; 當然，一個作者沒意識到的驚天漏洞也可能是突破P vs NP問題的關鍵。

在還沒有完全理清論文邏輯和證明細節，學者們就開始爭論，就發博客推文持立場，即便是著名學府的著名學者，那只是搶頭條，沒啥用。

不知道能不能從數學上證明，凡是試圖證明P=NP或者P≠NP的論文，都一定有錯誤。

作為理論計算機領域的壓軸大題，學界普遍認為P不等於NP(這句話可能不嚴格，感謝評論區)，但從未給出嚴格的數學證明。(聽說有教授將此題作為期末考試的加分題，萬一有學生做出來了呢，哈哈。)

個人認為將是個大新聞，不論證明正確與否。

雖然在美國碩士期間上整數規劃（運籌學分支，研究一堆NP難問題的精確解，指數級演算法）這門課的時候，系統學習過P vs NP，作業還變態地要求證明幾類問題是NP-complete （通過規約的方法）。

但是，我並沒有打算精讀這篇paper，更不打算在知乎上做技術點評。

以及這個問題2500+關注人數，卻只有8個回答。

原因如下。。

Robin Shen：如何看待知乎上某些PhD學生不好好做科研, 他們竟然在談，怎麼追女生，問題是他們好像沒談過戀愛？

真的關心paper細節？知乎大概不適合你，請前往下面技術站。

Is Norbert Blum"s 2017 proof that $P
e NP$ correct?

----------------------------------------------------

所以，我是來科普的。

關於NP vs P（以及NP-complete、NP-hard），花了半小時惡補了下概念，並「篩選」出下面這篇非常不錯的科普文，有興趣的不妨看看。

Matrix67: The Aha Moments

回到正題。。

如果證明正確？

那代表著七大千禧難題之一被解決，100w獎金到手--絕對世紀大新聞。（目前僅有龐加萊猜想被解決）

Millennium Prize Problems

錯誤？

那麼Norbert Blum教授將會very embarrassed。

當然必須沒有韓春雨老師 Nature撤稿這件事那麼「負面」（如果是造假的話）。

首先數學證明不存在實驗造假。

其次，科普一下arXiv.org這個網站。

通常是學者們在投稿後被期刊或會議接收前，把自己的論文掛在此網，為的是消除期刊審稿的這段真空期（有時長達倆年）。

換句話說，讓自己的科研成果早日公示於眾。

也就是說，這篇文章可能投到了某個期刊，在接受漫長的審稿過程（預計不下倆年審不下來吧）。

話又說回來了，作為一道價值100w美元的世紀難題，作者有勇氣掛在網上接受全世界的檢驗，應該已經是反覆驗證過幾百遍了的吧？

最壞的打算--驗證錯誤？

其實也沒有什麼大要緊的。

因為。。

Blum教授64歲了，而德國教授的退休年齡是65歲。。

退休前搞出個大新聞，不為自己，為母校波恩大學（德國）做個宣傳，我覺得也是值了。。

（波恩大學還有位德國歷史上最年輕的W3教授，[轉載]24歲數學天才成為德國最年輕教授_運河與大湖_新浪博客）

然後又看了下其近幾年發論文情況，2012至今只發表了倆篇文章。

有理由相信，是在憋大招。

dblp: Norbert Blum

-------------------------------------------------------------------------

再科普一下整數規劃、組合優化--運籌學的分支，研究NP難問題的精確演算法，通常是指數級演算法複雜度。

離散/整數/組合/非凸優化概述及其在AI的應用

混合整數規劃/離散優化的精確演算法--分支定界法及優化求解器

以及近似演算法--求解NPC問題近似解（有approximation ratio），通常是多項式時間演算法（上面文章里也有涉及）。

--------------------------------------------------------------------------

最後，個人還是希望證明是正確的。

因為，如果P = NP

那麼，我們這群研究NPC問題的學者，就沒飯吃了。。

--------------------------------------------------------------------------

最後的最後，從人工智慧、深度學習的熱潮中跳出來，鞏固一下理論知識。

我想也是極好的。

看不懂，但應該是錯的

https://arxiv.org/abs/1708.03486

The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage this http URL

這要是真的，波恩大學要火啊，據說明年的菲爾茨獎波恩大學的Peter Scholze已經預定了？

我堅信p=np。

文章及圖片，放在百度網盤上公開的https://pan.baidu.com/s/1mh6TMWw

平面圖3-著色問題（NP完全問題）的多項式時間演算法及不完整證明

湖南大學數學系胡錢元

摘要：本文給出了平面圖頂點3-著色問題的一個多項式時間演算法。文

章除了命題1沒有完整的證明（該命題如同「若爾當曲線定理」一樣看起來

顯然正確，但證明卻非常麻煩），其它所有部分都給出了數學上嚴格而且

完整的證明。由於3-著色問題是NP完全問題，任意一個NP完全問題若有

多項式時間演算法意味著所有的NP完全問題存在多項式時間演算法，因此本文

表明NP=P。

關鍵詞：平面圖，3-著色問題，多項式時間，演算法，NP完全問題

概述著名的「四色定理」說明，平面圖的頂點可以4-著色。但對

於任意平面圖G，判斷G的頂點可否3-著色是一個NP完全問題，哪怕

G的每個頂點的度都不大於4[1]。

平面圖的3-著色問題之所以困難，在於兩點：一、即使圖可3-著色，

但若其中存在不相鄰卻必須著色相同或不同的頂點，要確定這樣的頂點非

常困難（如果圖不可3-著色，則困難在於找到一個極小的色數為4的子

圖——該子圖去掉任意一個頂點及其所有關聯邊都可以3-著色）；二、即

使圖可3-著色，且其中任意兩個不相鄰的頂點可以著色相同或者不同，找

到一個多項式時間的3-著色方案也不容易。本文對這兩點一一做了分析，

給出了平面圖3-著色問題的一個多項式時間演算法，該演算法的時間複雜度不

超過O（n^10）。

由概述，先給出一些重要的定義，這些定義對於平面圖3-著色問題的

多項式時間演算法起到了關鍵作用。

定義（對等點）：設G=（V，E）是簡單無向圖，G的頂點色數

S（G）=3，va、vb是G中不相鄰的兩個頂點，若對G的任意一種正確的3-著

色方案，va、vb都著相同顏色，則稱「va、vb是G的一對對等點」（或

「G存在對等點va、vb」，「va（vb）存在對等點vb（va）」）。

例1.如圖1所示，G=（V，E），V={v1，v2，v3，v4}，E={（v1，v2），

（v1，v3），（v2，v3），（v2，v4），（v3，v4）},v1、v4是G的一對

對等點。

定義（比鄰點）：設G=（V，E）是簡單無向圖，G的頂點色數

S（G）=3，va、vb是G中不相鄰的兩個頂點，若對G的任意一種可行的3-著

色方案，va、vb都著不同顏色，則稱「va、vb為G的一對比鄰點」（或

「G存在比鄰點va、vb」，「va（vb）存在比鄰點vb（va）」）。

定義（理想圖）：設G=（V，E）是簡單無向圖，G的頂點色數S（G）=3，

若對G的任意兩個不相鄰頂點va、vb，存在對G的兩種正確的3-著色方案，

使得在這兩種方案中，va、vb的著色分別相同和不同，則稱G為理想圖。

由定義可知，理想圖中不存在對等點、比鄰點。並且容易知道理想

圖的任意4階子圖的邊數不大於4（否則G有對等點）。

更多細節見開始的鏈接。

參考文獻

[1]M.R.Garey,D.S.Johnson and L.Stockmeyer, Some simplified

NP-complete graph problems,Theoretical Computer Science(1976)

237-267.

簡單地說，這種問題還是別去證明了。既然沒有任何辦法在多項式時間內解決NP complete問題，就當解決不了（P != NP)。

然而，我相信，運用多項式的空間儲存domain specific的知識（例如用多層神經網路壓縮儲存圍棋中的大量模式），可以在多項式時間內，對大部分NP優化問題進行無限的逼近。（表音字的P→NP猜想）

For an NP problem with an exponential-time algorithm A, and any constant 0 &< ε &< 1, an algorithm A" exists which uses O(N^k) time and O(N^l) space to produce the same output as A with probability p &>= 1 - ε. (P→NP Conjecture from BYZ).

---- 新增於8/22/2017 ----

感謝大家的討論，指出這個問題和BPP(Bounded-error probabilistic polynomial time)問題有一定關係，但也有不同。總的來說，這個題目引出了兩個相關而且看似很重要的課題，這裡就當作拋磚引玉了。1）BPP只考慮一定比例輸入(如2/3)得到最優解，而不考慮輸入的概率分布。若考慮輸入的概率分布以及隨機演算法相關的複雜度問題，可以參考Yao"s principle，姚期智先生的大作。2）將機器學習和複雜度理論結合的理論還有大名鼎鼎的Probably Approximately Correct (PAC) learning。這個理論應用在Reinforcement Learning領域有PAC-MDP演算法，似乎Andrew Ng等人也進行過相關研究。