HP研究人员宣布P!=NP证明

作者 | 2010-08-09 21:27 | 类型 行业动感 | 9条用户评论 »

Sina WeiboBaiduLinkedInQQGoogle+RedditEvernote分享




image      计算机理论界第一号的问题，就是P是否等于NP的问题，多年来至今无解，它也是美国克雷研究所悬赏百万求解的难题之一。克雷研究所的七大难题，只有一个有解了，Poincaré Conjecture，被俄国数学家Grigoriy Perelman成功破解。

      最近，惠普实验室的研究人员Vinay Deolalikar博士，发布了一篇近百页的论文，宣称证明了P!=NP。仅凭直觉，P也不应该等于NP，同时，这位Vinay同学也不是民科，他美国南加大博士毕业，研究计算机理论多年，所以他证明正确的可能性还是存在的。当然，其证明正确与否，还有待于大量同行研究者的验证。

有兴趣的读者，可以进一步阅读:

百万美元悬赏：求解七大世纪难题

P=NP问题背景资料，Wikipedia

Vinay N!=NP论文

(2个打分， 平均：5.00 / 5)

工具箱
本文链接 | | 打印此页 | 9条用户评论 »

雁过留声

“HP研究人员宣布P!=NP证明”有9个回复

  1. 陈怀临 于 2010-08-09 9:32 下午

    不知这几天清华高能研究院的姚先生的心情如何。。。好奇的说。

  2. ikewu83 于 2010-08-10 1:30 上午

    学习中！

  3. wj 于 2010-08-10 7:02 上午

    理解成阶乘了。。。半天才反应过来。。。

  4. kk 于 2010-08-11 5:04 下午

    全世界的人都瞩目的题目，每年都有很多人宣称得到了答案。

    有什么关系吗？
    —————-
    陈怀临 于 2010-08-09 9:32 pm
    不知这几天清华高能研究院的姚先生的心情如何。。。好奇的说

  5. spike 于 2010-08-11 7:58 下午

    这个答案如果确定，对于计算机基础科学的影响有多大？当前的一些理论是不是大都是基于P ≠ NP 这个假设成立来做的？
    对于密码学加密解密系统会有比较明显的影响吧？比如不限长度的密码是不可以破解的，呵呵

  6. 陈怀临 于 2010-08-11 8:15 下午

    P!=NP不会造成太大的影响。因为大家都其实这样认为。。。如果我的P=NP，这个世界就乱了。。。会有哲学层面的混乱。。。chaos效应。

  7. ikewu83 于 2010-08-11 8:36 下午

    期待首席早日搞定P=NP，最好，我能拿我的股份来换将来论文上的名字。

  8. 陈怀临 于 2010-08-11 8:56 下午

    今天晚上开写。先finish中文稿吧。Stay tuned。

  9. carane 于 2010-08-12 11:20 上午

    也许应该转向这样一个方向：

    “P!=NP”是一个哥德尔命题。