闵应骅的博客分享 http://blog.sciencenet.cn/u/ymin 一位IEEE终身Fellow对信息科学及其发展的看法

博文

计算机科学界的大新闻(101031)

已有 3687 次阅读 2010-10-31 16:31 |个人分类:计算机|系统分类:论文交流| 计算复杂性

计算机科学界的大新闻(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已经可以处理上百万变量的布尔表达式。但这个问题的理论意义是无容置疑的。我们国家也有人涉足过这个问题,也有人给出过比较长篇的证明。但是,送给某些国外权威学者,他们基本上不看。一个是找证明中的错误是非常费劲的事情,人家不愿意干。另一个原因是根据证明者的背景和基础,就不像能证明如此重大问题的人。的确,牵涉这样深刻的问题,没有很强的数学基础是不可能解决的。你甚至不知道从何下手。就像有人连图灵机理论都不懂,就想推翻图灵机理论,有人讽刺说:“真是无知者无畏”。研究基础对于解决重大科学问题是绝对必要的。  

http://wap.sciencenet.cn/blog-290937-379073.html

上一篇:创新需要环境支持(101022)
下一篇:看了“铁梨花”(101112)

11 赫英 许浚远 傅云义 黄富强 唐常杰 程冬 agreatboy wenmei zhangzhi tubie bread0053

发表评论 评论 (11 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-4-13 07:30

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部