惠普研究员Vinay Deolalikar声称证明P!= NP

ugmbbc发布于 2010-08-09 22:06:33|154 次阅读 字体：大 小 打印预览


感谢昭的投递
新闻来源:cnblogs
惠普研究实验室的研究员Vinay Deolalikar声称证明了P!= NP。 P/NP问题涉及的是复杂度类P与NP的关系，P事实上是NP的一个子集，NP是指非确定性图灵机在多项式时间内计算的问题，而P是指确定型图灵机在多项式时间内解决的问题。P是否等于NP是克雷数学研究所的千禧年大奖难题之一。

Deolalikar的论文长达100页，目前尚 未经过同行审议，因此任何人都可以在论文中寻找漏洞或错误。如果Deolalikar的证明是正确的，那么他将有资格获得克雷提供的百万美元奖金。

相关内容在Greg的博里也有。

http://gregbaker.ca/blog/2010/08/07/p-n-np/

下面附上Deolalikar的邮件内容：


Dear Fellow Researchers,

I am pleased to announce a proof that P is not equal to NP,which is attached in 10pt and 12pt fonts.

The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof.

This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible.

This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.

Comments and suggestions for improvements to the paper are highlywelcomed.