“P!=NP”:这次真得被证明了吗?(转载)

 

 

“P!=NP”:这次真得被证明了吗?

 

 

 

     最近惠普实验室的研究员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://www.sciencenet.cn/blog/user_content.aspx?id=351664
Advertisements
此条目发表在Uncategorized分类目录。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s