首页 >> 资讯 >> 资讯 数学 >> 文章

turing machine 惠普实验室的研究员Vinay Deolalikar,一位在理论计算机、随机过程、代数和逻辑方面都有过贡献的研究人员,声称证明了P不等于NP。他的证明目前只有初稿在网络上流传,他在自己的网站上宣称将在近期贴出正式的论文。

P vs NP是克莱研究所的千禧年难题大奖中宣布的7道数学世纪难题中的一道。这7道难题分布在数学的不同分支,任一道难题的解决都被认为会对相应的分支有重大的影响。P vs NP问题属于理论计算机这个数学分支。 目前为止,这七道难题中唯一被确认证明的是庞加莱猜想,2006年由俄罗斯数学家格里戈里·佩雷尔曼证明。如果Vinay Deolalikar的证明正确,他将很有可能成为第一位领取千禧年难题百万大奖的人(佩雷尔曼拒绝了百万奖金)。

P vs NP问题,简单地说,就是是否每一个容易验证正确性的问题都能很“快”地计算出来?比如说,要验证一个整数是否整除另一个整数是很“快”的,那么给出一个整数,是否能很“快”找出它的一个因子?这里的“快”在理论计算机中有严格的定义,就是所需时间小于一个关于输入长度的多项式,我们也说这个算法可以在多项式时间内解决这个问题。这里牵涉的是算法的时间复杂度,“快”不是绝对意义上的,只是从级数上(主要是和指数级)的比较。

P的正式称呼是“确定性图灵机多项式时间复杂度”,而NP则是“非确定性图灵机多项式时间复杂度”。在理论计算机中,“判定问题”是这样的一类问题,对于某个输入,我们只需要输出“是”或者“否”作为答案。P和NP都是判定问题所组成的集合。如果对于一个判定问题,存在一个能在多项式时间解决它的算法,那么这个判定问题就在P中。如果对一个判定问题,存在一个算法,对于一个肯定的输入,都有一个“旁证”,而算法可以在多项式时间内利用旁证对这个输入进行正确的肯定判定,那么这个判定问题就在NP中。

P vs NP问题,问的正是P是否等同于NP。我们知道,NP包含P,但是在NP中有一类叫NP-完全的问题,至今都没有算法可以容易地解决它们。如果这些问题中有一个属于P的话,NP就等于P;否则,NP就不等于P。P vs NP问题在理论计算机中占有重要的地位,虽然至今为止还没有人确切证明出P是否等于NP,但是主流的推测是P不等于NP,很多应用算法就是基于这样的假设,而许多加密算法的保密性也是建立在P!=NP的前提上的,比如说著名的RSA。P vs NP问题的解决无论对于理论还是实践都有很大的影响。

Vinay Deolalikar的证明横跨了统计、逻辑、统计物理、计算复杂度等学科。他从一个NP-完全问题——可满足性问题(SAT)——入手,尝试证明没有算法可以容易地解决这个判定问题。他先将问题的解的统计特性与一个逻辑模型联系起来,再利用逻辑模型得到一个对算法计算时间的限制。然后他用统计物理的工具,得到了对一类输入——随机kSAT输入——的解的统计特性,将这个统计特性注入此前的逻辑模型中,他证明了对随机kSAT输入,没有算法在多项式时间内解决可满足性问题,从而证明P不等于NP。

现在仍不能确定Vinay Deolalikar的证明是否正确。他已将证明用电子邮件发到数位不同领域的专家手上审核。在惠普实验室他的个人页面上,他发表了一个声明,澄清在网上泄露的证明只是初稿,专家的审核尚未完毕,一个最终的版本会在近期内发布。

尽管P vs NP相当困难,此前也有不少人对它进行过失败的尝试,但对于这个来自这个领域研究人员的证明还是有希望的,让我们拭目以待。

Greg Baker关于这个证明的博客、 Vinay Deolalikar在惠普实验室的个人主页

“P vs NP” ,对于很多童鞋来说算是学到的一个新词儿了。它是什么意思?尽管看过介绍,也许你和小编一样还是一知半解(其实一头雾水),尽管这个证明已经被普遍认为不对了,甚至没有什么价值,也就是说,既不能提供什么新的思路,也不能退而求其次被改造成某个稍微不太重要一点的结论。但通过松鼠木遥讲述,这场史无前例的为期一周的web 2.0式的学术讨论简直就是个松鼠论坛高级版。楼主是惠普实验室一科学小青年,据说证明了出了一个“20世纪千禧难题”,迅速红遍全球。其他数学家奔走相告,但是帖子后面甚至连个“沙发”都没有。这篇长达102页的数学论文即便是顶尖的数学家也要研究上两天,不看出个所以然来他们是不会轻易“灌水”的。两天以后,这个帖子才一下子沸腾起来了,圈儿里响当当的名字纷纷“强帖留名”:Richard Lipton嫣然一副斑竹的架势;陶哲轩还客串技术支持搭建了个wiki 架构的页面……

消息来源:原创

作者:fwjmath

木遥Robot 审稿

想分享科技新鲜事,跟大伙儿谈论热点话题背后的科学?却懒得写长文章,或不知怎么参与?现在可以编译短文或写原创小文章,投稿给资讯频道,与大家共享信息。  详情 >>

0
为您推荐

28 Responses to “惠普实验室研究员声称证明世纪数学难题P!=NP”

  1. fwjmath说道:

    沙发~~~

  2. Eagle_Fantasy说道:

    沙发
    希望这证明最终被证实为真的能证明P!=NP

  3. 王一说道:

    没看懂这句话:

    “但是主流的推测是P不等于NP,很多应用算法就是基于这样的假设,而许多加密算法的保密性也是建立在P!=NP的前提上的,比如说著名的RSA”

    从字面意思,这句话我理解为:(1)假设P!=NP。(2)将来有可能快速计算P问题。(3)即便如此,很多加密算法,例如RSA,仍然是安全的。

    但是给我的感觉是,加密算法往往是P问题,不是NP问题。例如RSA依赖大质数因式分解,应该是个P问题,如果P!=NP,则此加密方法可能很快被破译。或者是我理解不对?

    我完全是外行,可能问题太naive了,见笑,呵呵

    • digiter说道:

      整数分解因子的问题现在还没有多项式时间的算法,RSA的加密算法是P的,但是破解算法(不是解密算法)目前还都是NP的

    • ikarienator说道:

      RSA不是一个好例子。传统RSA算法基于大数分解,这个问题至今没有多项式算法,但是也没有被证明是非P问题。因此传统RSA并不能由于NP!=P而变得安全。如果找到了大数分解不小心变成了P问题,那么传统RSA就倒塌了。不过我们依然有RSA的变体来保证NP。

      回复“整数分解因子的问题现在还没有多项式时间的算法,RSA的加密算法是P的,但是破解算法(不是解密算法)目前还都是NP的”: 是不是NP不是有没有多项式时间的算法决定的,而是需要证明。

      另外,就算是NP问题,哪怕NPC问题,很快都会变的不困难。因为量子计算机在本质上可以快速的解决任何的NP问题。那时必须使用NP-Hard来进行安全算法的设计才行。

    • ikarienator说道:

      RSA不是一个好例子。传统RSA算法基于大数分解,这个问题至今没有多项式算法,但是也没有被证明是非P问题。因此传统RSA并不能由于NP!=P而变得安全。如果找到了大数分解不小心变成了P问题,那么传统RSA就倒塌了。不过我们依然有RSA的变体来保证NP。

      回复“整数分解因子的问题现在还没有多项式时间的算法,RSA的加密算法是P的,但是破解算法(不是解密算法)目前还都是NP的”: 是不是NP不是有没有多项式时间的算法决定的,而是需要证明。

      另外,就算是NP问题,哪怕NPC问题,很快都会变的不困难。因为量子计算机在本质上可以快速的解决任何的NP问题。那时必须使用NP-Hard来进行安全算法的设计才行。

  4. luojianchuan说道:

    帖子说:“我们知道,NP包含P,但是在NP中有一类叫NP-完全的问题,至今都没有算法可以容易地解决它们。如果这些问题中有一个属于P的话,NP就等于P;否则,NP就不等于P。”

    这里的“否则”在逻辑上似乎应该理解为:“如果这些问题中全部不属于P的话,NP就不等于P。”

    惠普的研究员只提供了一个反例,这并不足以构成证明。是否介绍 P vs NP 有错?是否应为“我们知道,NP包含P,但是在NP中有一类叫NP-完全的问题,至今都没有算法可以容易地解决它们。如果这些问题中全部属于P的话,NP就等于P;否则,NP就不等于P。”——毕竟惠普男那么 serious 写了 100 多页,不太可能是他错了。

    • fwjmath说道:

      从NP-完全问题的定义,可以推出只要有一个NP完全问题不属于P,那么NP就不等于P。NP完全问题的另一个特色就是,在某种定义(多项式时间规约)下,它们的难度是完全相同的,一个在P里边就所有都在P里边,一个不在P里边就所有都不在P里边。

      这里可能是我写得不够清楚,不过陈述的都是事实。

  5. 王一说道:

    不好意思,发现自己理解错了,理解反了P的含义,现在明白了。不过文章中P和NP的概念是理解文章的关键,这里的定义有点专业,可否加几句注解,讲得易懂些?这些大概是计算机专业的基本概念吧?不过对于外行,还是需要花些功夫理解的 😉

  6. CouponLink说道:

    这个境界太高了~

  7. forinec说道:

    作为同事,表示鸭梨很大。。。

  8. noddy说道:

    如果这篇文章经过验证是正确的,那该是令人非常激动的消息了

  9. snowmantw说道:

    敢問各位先進像 NP != P 這樣的複雜度問題是否僅建立在傳統計算機上,或是對像由疊加、纏結等工作為原理的量子計算機也適用?

    • fwjmath说道:

      上面的复杂度是对于传统计算机(或者说图灵机)而言的,不能直接用于量子计算机。量子计算机有不同的时间复杂度定义和概念,比如说BQP等。

  10. fan说道:

    总觉得文中的那些专业名词看起来别扭(当然我一直学英文原版教材,也许名词的中文翻译确实是这些)。

  11. xuehui869说道:

    这个也是9号上午知道的,巧的是前几天还一直看这个问题

  12. ak47aug说道:

    太帅了~~这绝对是复杂度领域的里程碑式的发现~

  13. 烛嗔泪说道:

    到底是P! vs NP 还是 P vs NP??

  14. lbaby说道:

    这个牛啊, 激动

  15. thynson说道:

    那份论文在我手上我会到处说么。。。

  16. badwin说道:

    这个如果被证实是正确的证明,真是太牛了!

  17. 囧呢森说道:

    涉及复杂的逻辑啦数学啦之类的东西真的是完全没办法理解…TAT

  18. strolleronline说道:

    我是属于NP=P派的,我相信绝大多数NP问题都可以转化为P问题

  19. [...] “P vs NP” ,对于很多童鞋来说算是上周学到的一个新词儿了。它是什么意思?尽管看过介绍,也许你和小编一样还是一知半解(其实一头雾水),尽管这个证明后来被认为是错的,甚至没有什么价值,但通过松鼠木遥的讲述,这场史无前例的为期一周的web 2.0式的学术讨论简直就是个松鼠论坛高级版。楼主是惠普实验室一科学小青年,据说证明了出了一个“20世纪千禧难题”,迅速红遍全球。其他数学家奔走相告,但是帖子后面甚至连个“沙发”都没有。这篇长达102页的数学论文即便是顶尖的数学家也要研究上两天,不看出个所以然来他们是不会轻易“灌水”的。两天以后,这个帖子才一下子沸腾起来了,圈儿里响当当的名字纷纷“强帖留名”:Richard Lipton嫣然一副斑竹的架势;陶哲轩还客串技术支持搭建了个wiki 架构的页面…… [...]

  20. zhenzhen_sofia说道:

    想看论文原文。。。

  21. 高明利说道:

    百度百科中的“太极计算”,其中有NP=P的太极证明、太极计算推导出的勾股扩展定理以及质数方程、大质数及大合数双质因数问题的太极分析等,请比较一下那个结论更合乎逻辑。

  22. freepublic说道:

    比较好证,比四色定理简单.
    早就证明了,难度适中
    http://vixra.org/abs/1303.0192

Leave a Reply