呼叫高手出来八一八，P＝NP搞定了

My research can be broadly divided into basic and industrial.

BASIC RESEARCH

Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt).  Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning.  The preliminary version made it to the web without my knowledge.  I have made minor updates, here. Please note that the  final version of the paper is under preparation, and is to be posted here very shortly. Stay tuned.

回楼上，在Twitter上T1说 “Hem....居然在50岁之前，看到了费马大定理,庞加莱猜想,N!=NP.能不能看到有人搞定Riemann 猜想?”。我让他来八一八，大牛不理我，呵呵。

My initial impressions are that the paper does not raise any of the usual and obvious “red flags” that accompany the majority of proposed solutions to famous problems, but also does not yet align comfortably with the established progress on this problem (in particular, the focus on the properties of random k-SAT seems to be incongruous with what we have learned from the work of Razbarov and Rudich, even if it may technically be compatible), or on related problems in complexity theory.

一位 HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题，得出了 P≠NP 的结论。 P 是否等于 NP ，这是计算机科学领域中最困难的问题之一，也是意义最深远的问题之一，长期以来一直备受争议。如果这个问题获得解决，将会在各个科学领域中引起轰动。 Vinay Deolalikar 的整个证明有 100 多页，详细的论文可以在这里看到：

      http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf

    Stanford 的博士后 randomwalker 看完证明后表示，很多迹象表明，这个证明很有可能是正确的。

 

转一个陶帅哥的Comments



这是一个None Contructive的证明,对于许多搞complexity theory的人来说不是太舒服。

惠普研究所首席科学家Vinay Deolalikar声称证明了P!= NP。一时激起了千层浪，他的证明引发了广泛的关注和热烈的讨论，甚至《自然》网站也关注了此事的进展。其他数学家已经从他的原始论文中发现了很多小错误，提出了几个还没有解决的大问题（该Wiki页会不时更新）。 Vinay Deolalikar在过去几天也对论文进行了多次修改：8月6日他将自己的手稿(PDF)首次发给了多位业内专家；8月9日他更新了论文草稿(PDF)；8月10日他从自己的主页移除了所有提及P!=NP证明的内容和论文，不过论文还是可以从他的Papers子目录下找到。一些人认为，他的论文提供了一种新思路，但也包含了很多漏洞，P!=NP证明并未完成。