P!=NP，新的图灵大牛要诞生哇

还是等官方消息吧

这个求解释…

看不懂~~

9# weiwlw
有一篇100页的论文。。纯看不懂。。
joshua.cong 发表于 2010-8-11 23:17

我根本就不试图去看这种论文

从P≠NP得到P=HP

三哥的证明基本是错的了，不过不知道到底能对complexity theory做点儿贡献

陶哲轩等5人组成的小组验证论文的结果：
http://rjlipton.wordpress.com/20 ... p%E2%89%A0np-proof/

the consensus seems to be best summarized by a recent comment here by Terence Tao:

I think there are several levels to the basic question “Is the proof correct?”:

1. Does Deolalikar’s proof, after only minor changes, give a proof that P !=  NP?
2. Does Deolalikar’s proof, after major changes, give a proof that P !=  NP?
3. Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added.” But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days.)

话说陶哲轩涉猎真广，最近几年还发STOC，FOCS。。。抢广大计算机同学的饭碗呀 ：）

要火了.

15# cliff 呵呵，回复好犀利

其实貌似每年都会有人自称证明了P!=NP，只不过这一次引起比较大的轰动而已。