如何评价波恩大学 Norbert Blum 关于 P≠NP 的证明?

文章见: [1708.03486] A Solution of the P versus NP Problem 能不能解释一下证明的过程与争论的焦点呢?
关注者
2,703
被浏览
189,976

11 个回答

目前学界对此较为谨慎,需要等待同行的审查和评定。


题主在问题描述中写道:

能不能解释一下证明的过程与争论的焦点呢?

恐怕这有点困难,因为如果读者不是长期研究这个领域,三言两语难以阐述清楚。若是大家真的有兴趣,可以参考文末的几个链接。

想浏览最新进展的话,大家可以跟进 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号写的,他在回答中也一再说明这仅仅是个人观点。


一些较为正式的参考链接:

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.

所以看起来事情还没有定论 :P