阿赛空间分享 http://blog.sciencenet.cn/u/gpan

博文

“P!=NP”:这次真得被证明了吗?【最新进展!】 精选

已有 13661 次阅读 2010-8-10 15:07 |个人分类:七嘴八舌|系统分类:科研笔记|关键词:P/NP问题; 计算理论

 

【最新进展08.11】 

    佐治亚理工学院Richard Lipton教授正召集成立一个由国际顶级专家组成的group对Deolalikar的工作进行讨论并尝试帮助他修补证明中存在的问题,该group包括Richard Lipton,Timothy Gowers, Gil Kalai, Ken Regan, Terence Tao, Suresh Venkatasubramanian 等数学界及计算理论领域的大人物。其中Terence Tao就是那位24岁便被美国加州大学洛杉矶分校(UCLA)聘为正教授、2006年31岁即获得数学最高荣誉“菲尔茨奖”的数学界传奇人物暨华裔陶哲轩。 目前同行们已发现现有证明中存在若干问题。该Group倡导大家能“keep the tone constructive and supportive”。

    根据Lipton教授跟Deolalikar的个人直接交流,Deolalikar目前正忙于修改论文。Deolalikar目前已暂时将论文信息及链接从其个人主页撤下。但论文实际上还在
其主页空间中。

===============================================================

      最近惠普实验室的研究员Vinay Deolalikar声称已经证明“P!=NP”,并网上公开了论文草稿。他已在8月6日私下将100来页的论文草稿发给了相关研究领域的若干主要研究者审查。目前尚未通过同行审议。

 
    该消息已得到国际同行的强烈反响。美国计算机科学家Richard Lipton于美国时间8月9日在其个人博客上将计算理论及数学界同行们对该论文极其初步的反馈意见做了部分汇总,疑问暂总结为4个问题。
 
    Vinay Deolalikar出生于1971年,本科硕士毕业于孟买的印度理工学院(Indian Institute of Technology, Bombay),号称印度的MIT。博士1999年毕业于美国南加州大学(USC)。
 
    P vs NP问题 是计算理论领域乃至整个数学领域的皇冠级问题,至今没有解决。该问题在1971年由Stephen A. Cook和Leonid Levin分别独立提出,即“P类与NP类是否恒等?”。通俗地讲,P类问题是指那些可以在多项式的时间里找到解的问题,NP类问题是指可以在多项式的时间里验证一个解的问题。目前为止,人们一直没法证明P类是否等于NP类。但大多数计算机科学家更倾向于 P!=NP
 
    P vs NP问题是“克雷数学研究所”(Clay Mathematics Institute, CMI)的七个千禧年大奖难题之一。 http://www.claymath.org/millennium/P_vs_NP/
 
    CMI列七个千禧年大奖难题,不仅因为难度,更因为其对理论发展的重要性,它们分别是:
 
  •  Birch and Swinnerton-Dyer Conjecture(贝赫和斯维讷通-戴尔猜想)
  •  Hodge Conjecture(霍奇猜想)
  •  Navier-Stokes Equations(纳维-斯托克斯公式)
  •  P vs NP(P/NP问题)
  •  Poincare Conjecture(庞加莱猜想)
  •  Riemann Hypothesis(黎曼假设)
  •  Yang-Mills Theory(杨-米尔斯理论)
 
    这七个难题中,目前仅庞加莱猜想在2006年确认由俄罗斯数学家格里戈里·佩雷尔曼证明。注意,大家熟知的哥德巴赫猜想并不在其中。
 
     进一步了解P/NP问题,可参考Wikipedia中文   Wikipedia英文

 



http://blog.sciencenet.cn/blog-28351-351664.html

上一篇:快女"曾轶可"的成名"原创歌曲"抄袭铁证如山了
收藏 分享 举报

10 邹晓辉 俞立 梁进 黄富强 杨正瓴 高建国 唐常杰 武京治 罗军 杨华磊

发表评论 评论 (21 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2017-10-20 05:56

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部