计算机科学界的大新闻(101031)
闵应骅
绝对是计算机科学界的大新闻,P≠NP已经证明了。
惠普实验室的研究员Vinay Deolalikar(出生于1971年,孟买的印度理工学院的学士和硕士,1999年获美国南加州大学(USC)博士学位)声称已经证明“P≠NP”,并在网上公开了论文草稿。他在8月6日私下将100来页的论文草稿发给了相关研究领域的若干主要研究者审查。佐治亚理工学院Richard Lipton教授召集成立了一个由国际顶级专家们组成的group对Deolalikar的工作进行审查。该group包括一位数学界华裔传奇人物陶哲轩。他24岁被美国加州大学洛杉矶分校(UCLA)聘为正教授、2006年31岁即获得数学最高荣誉“菲尔茨奖”。Richard Lipton在8月15日发表一篇博客,说这问题已有重大进展,可以分裂为若干子问题。8月16日纽约时报也发表文章,说该问题的主要障碍已经突破。
P≠NP是一个计算复杂性的问题。能够在多项式的时间里找到解的问题称为P问题,在多项式的时间里只能模拟验证,而不能确定在多项式时间内找到解的问题称为NP问题。长期以来,计算科学界证明不了这两类问题是否重合,还是排斥。P vs NP问题成为克雷数学研究所七个千禧年大奖难题之一。
当然,从工程的角度说,P问题不见得不复杂;NP问题也不见得就那么复杂、不可解。例如计算(10n)的1000次方是一个P问题,但是,n较大时,多么大的计算机也是无法计算的。另一方面,布尔可满足性(SAT)问题(参见
http://www.sciencenet.cn/m/user_content.aspx?id=255116)是一个典型的NP问题,但现在工业界的SAT Solver已经可以处理上百万变量的布尔表达式。但这个问题的理论意义是无容置疑的。我们国家也有人涉足过这个问题,也有人给出过比较长篇的证明。但是,送给某些国外权威学者,他们基本上不看。一个是找证明中的错误是非常费劲的事情,人家不愿意干。另一个原因是根据证明者的背景和基础,就不像能证明如此重大问题的人。的确,牵涉这样深刻的问题,没有很强的数学基础是不可能解决的。你甚至不知道从何下手。就像有人连图灵机理论都不懂,就想推翻图灵机理论,有人讽刺说:“真是无知者无畏”。研究基础对于解决重大科学问题是绝对必要的。
https://blog.sciencenet.cn/blog-290937-379073.html
上一篇:
创新需要环境支持(101022)下一篇:
看了“铁梨花”(101112)