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

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)

雁过留声

“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”是一个哥德尔命题。