P != NP

本来这阵子在筹划写点别的blog，后来发现这条新闻，实在很是有分量。

相关链接可以参见 这里 。也欢迎到 作者主页 打酱油。虽然 Clay数学研究中心 还没有对该论文结果做出正式回应，不过看来已经基本尘埃落定了。

大概扫了一眼这篇论文的Introduction，作者本人说，本证明过程牵扯到了很多数学和物理的领域（This proof requires a convergence of ideas and an interplay of principles that span several areas within mathematics and physics）。这篇66页的论文也许就此宣告众多计算理论学家的工作就此结束。

既然P不等于NP了，那么以后遇到一个问题很难找到多项式时间解，大家就可以尝试证明该问题是NP完全问题。如果是NP完全的，大伙就不用费事去找多项式时间解了。那些醉心于美妙的多项式算法的学者们可能略显沮丧。不过这也许让研究随机算法的人多了几分动力。因为既然没有多项式算法，那么就只能找个还算能接受的随机算法。个人感觉在这种随机算法还是很有前途的——哪怕是在量子计算机时代。至于密码学家们，总算可以松了口气。要破解基于NP完全问题的密码系统，恐怕只能等量子计算机出现之后再说了，好在到时候已然有了量子加密技术。至于搞量子计算机的朋友们，可以就此表示：俺们的量子计算机那就是真NB！至于哲学的影响，恐怕就是要说：的确有些问题是“难”的，而且这个“难”已经不再是感性上的“难”。

不过一切倒也还好，因为理论界早就普遍相信P不等于NP了。这次的证明只是（可能）证实了这一点。想必大伙也早就有准备。

顺便再说一句，如果Clay数学研究中心证实了该结果为真，那么此牛人即将获得$1M的奖金。不过对于如此大牛，这些身外钱财恐怕早就不放在眼里了。大牛说：杂念！玩儿蛋去吧！

后记：

证明出这结论的猛男，现供职于惠普实验室。71年生人。从其经历上看，他在印度科学院拿得硕士。由此可见应该是个印度人。硕士论文的方向是神经网络。博士在南加州读的，主修EE，辅修数学。在惠普实验室主攻数论，代数几何，编码，机器学习，随机过程，数字通信等。证明P是否等于NP这工作并与他在惠普实验室的工作无关，他表示，俺就是个玩票的。在他给各位研究人员发的 邮件中 ，是这么陈述的：This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. 广大计算理论的研究人员啊，这叫大伙情何以堪啊！