邓楠

邓楠的博客

他的个人主页  他的博客

P != NP

邓楠  2010年08月09日 星期一 11:43 | 1414次浏览 | 0条评论

2010年8月6日,惠普实验室的Vinay Deolalikar发表了论文,证明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. 广大计算理论的研究人员啊,这叫大伙情何以堪啊!

评论

我的评论:

发表评论

请 登录 后发表评论。还没有在Zeuux哲思注册吗?现在 注册 !

暂时没有评论

Zeuux © 2019

京ICP备05028076号