当今世界计算机领域人才分布兼论Vinay Deolalikar“P!=NP” 的证明 (转载)

 

 

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

 http://www.hpl.hp.com/personal/Vinay_Deolalikar/

 

敝人先就他的证明说两句。

 

大家知道,P是否等于NP,属超级难题,一直未解。不少人声称已解决该难题,但未被认可。如今的 Vinay Deolalikar 声称已经证明P!=NP”,前景如何?

 

关于P对NP问题,目前有三种观点:1,认为P!=NP,2,认为P==NP,3,认为无法确定,甚至人类永远无法确定。第一类是主流。

 

先谈他的优势:英文表达很溜,英文论文的写作水平,结构及表达方式一流,因而很吸人眼球;拥有惠普实验室的研究员的头衔,之前已有不少带原创价值的成果;跨多学科,知识广泛,idea新颖;论文洋洋万言,长篇大论,符合此类论文的特点;结论符合大多数主流权威专家的看法。

 

再谈可能的问题:简单的逻辑是,证明越单一,越简洁,越易于被确定,而越复杂越“倒腾”,越易将人搞糊涂,包括将他自己搞糊涂。他采取的是跨多学科,将多种不同源的概念原理连接起来,综合得出证明结论的方式,方法新颖,具有创意,之前从未有人想到过,因而易引起关注和敬畏。然而,恰恰是这些可能使他陷入深渊:1,因跨多学科,他自己对其他学科相应的概念原理理解的深度和准确度的问题;2,多学科概念原理连接时,概念原理在内涵外延上衔接会否出现缝隙问题;3,他用的是抽象的理论推导,抽象的概念原理堆砌,将一个领域的概念原理应用到另一个领域时,在对概念原理的应用适当性方面的理解会否出现根本性偏差的问题,若是,则从根本上动摇了整个证明。

 

当今世界计算机领域人才分布是:美国是当然的老大,而且不断地从老二老三那里吸走大量人才,其次日本欧洲甚至韩国在许多应用领域拥有强大的实力。除老美外,中国印度应是列第二位的计算机人才大国。美国各大学计算机专业外国的研究生人数包括一些计算机公司外国职工的人数,基本上都是中国印度排在前面。就人数而言,中国多于印度。但印度往往出创造型人才,中国则出不了。那个拿图灵奖的YAO,其用以拿奖的论文要说有多少创造性和突破性也谈不上。为什么?我仅举一个小例子:当年我在学校遇到一印度老师,一中国老师。印度老师非常明显,对印度学生最好,其次是美国学生,对其他国学生尤其是中国学生最差。而那位中国老师则相反,他只敢对中国学生耍威风,见了美国学生则非常恭敬客气,生怕美国学生Complain他,课堂上若是美国学生提问,他长时间客气地回答或与之讨论,而若中国学生提问,他则明显的不耐烦。此点深深体现代表了一种民族劣根性。

 

那个困扰了世界多少年的难题,素数的判定问题,原来一直以为是指数型的,前些年两个印度佬搞出了一个算法,证明可以用多项式求解。如今的这个NP难题,难道又要为印度佬所破?当然,我是属P=NP派,我认为他肯定错了!

 

 

 

本文引用地址: http://www.sciencenet.cn/m/user_content.aspx?id=351874

Advertisements
发表在 Uncategorized | 留下评论

“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
发表在 Uncategorized | 留下评论

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!

发表在 Uncategorized | 留下评论