首页
社区
课程
招聘
惠普研究员称已解决计算机科学第一难题:N=NP?
发表于: 2010-8-11 16:22 8638

惠普研究员称已解决计算机科学第一难题:N=NP?

2010-8-11 16:22
8638
转自:http://news.csdn.net/a/20100810/277993.html

【Csdn 综合报道】(文/刘江)这几天惠普新闻不断。其实技术人员更应该关心的,不是那个CEO的绯闻女郎是否漂亮,CEO是否因公司政治蒙冤下台,而是另一件可能会名垂青史的大事:一位名为Vinay Deolalikar的70后印度籍惠普研究员8月6日在自己的网站发布了一篇名为“P is not equal to NP”的论文(点击下载),也就是说,他认为自己证明了P不等于NP!

学过计算机科学理论的人都应该知道,计算机科学中有一个天字第一号问题一直没有解决,引得无数图灵奖得主和顶级计算机科学家竞折腰,这个圣杯就是P/NP问题。事实上,这个问题也位列Clay数学研究所重金征解的七大数学难题之首,与我们凡夫俗子也多少知道的黎曼假设和庞加莱猜想并列。解决其中任何一道难题,都可以得到100万美元奖金。其中,庞加莱猜想已被我们时代最伟大的Geek格里戈里·佩雷尔曼于2002年解决。

简单的说,P问题是指能找到迅速(准确地说是多项式时间内)解决算法的问题,P是Polynomial(多项式)时间的第一个字母。而NP问题,是指这个问题的解能够迅速(准确地说是在多项式的时间里)猜测并验证,但是很难找到,NP是Nondeterministic Polynomial (非确定多项式)的首字母缩写。所以,P=NP?问题实际上是要证明或者推翻,P问题和NP问题不等价。由于NPC(NP-Complete)问题的存在,学术界普遍认为P不等于NP,但始终无法给出令人满意的证明。

现在,Vinay Deolalikar宣布自己摘取了这项桂冠。他已经将论文发给多位各个领域的顶尖专家进行同行评审。

Deolalikar在信中写道:

亲爱的同行:
我很高兴发布一个关于“P不等于NP”的证明,证明附后。
这个证明用到了数学多个领域的原理,主要工作是发现了在不同领域之间一系列概念联系,并用统一的透镜观察。其次就是证明中每一步骤遇到的技术性困难了。
这项工作建立在许多受人尊敬的研究者的基础性贡献之上。这篇论文中,我有意阐述了理解证明所需的全局性框架,并尽可能减少了技术性和计算性的细节。
这项工作是在我担任惠普研究院研究员的业余时间独立完成的。在此之前的过去两年中,我已经试图使用其他的概念组合,进行了几次不成功的尝试。
非常欢迎大家对论文进行评论,提出改进意见。
目前此事尚没有得到任何正式的确认。不过,这个问题的提出者、图灵奖得主Stephen Cook评论,(Deolalikar的)“声明看上去比较严肃”。

MIT的助理教授Scott Aaronson(他曾经写过一篇文章《所谓数学突破的十个错误标志》)显然不太相信这个问题能比较容易地解决,他发表博客,表示如果Deolalikar被授予了100万Clay千禧大奖,他愿意个人掏腰包再奖20万美元。

著名的计算理论博客、佐治亚理工学院计算机科学教授Dick Lipton也发表文章简单解释了论文的思路,认为这项工作是严肃的。Lipton在文中说,Deolalikar是通过有限模型理论搭桥,引出反证,用到了Moshe Vardi (1982) 和Neil Immerman (1986)的结论。

8月9日,Lipton又综合已有的对论文的评论,发表了新的文章,认为证明肯定存在错误,但他又表示,这是任何突破性研究都无法避免的。该证明的策略是否证明,存在的问题是否能够修正,仍然有待研究。

此外,犹他大学计算机学院的助理教授Suresh Venkatasubramanian通过Google Docs(链接,可能无法访问)来讨论这一证明,充分利用集体智慧,你也可以加入!文档本身应该是LaTeX格式的。

CSDN博客专家袁泳在Twitter上分析了Deolalikar的思路,“是通过编码K-SAT构造某种有序结构。如果NP=P,那根据Vardi的定理,K-SAT能用FO(LFP),也就是最小不动点的一阶逻辑表达,也就说存在某个多项式时间基于LFP的算法。但是该结论同K-SAT的某些统计性质矛盾。”但他也表示自己的知识不足以评价甚至看懂这篇论文。

Vinay Deolalikar是否真的解决了计算机科学界目前的最大问题呢?让我们拭目以待。如果你看懂了这篇论文,请与我们联系。

【CSDN小百科】
Vinay Deolalikar,1971年出生于印度新德里,1994年在孟买印度理工学院获得电机工程硕士学位,1999年在南加州大学获得电机工程和数学博士学位。他的研究兴趣是数论、代数几何及其在编码理论中的应用,机器学习与数据挖掘及其在信息管理中的应用,数理逻辑,随机过程,统计学,数字通信等。他在惠普研究院网站上的个人网页是:http://www.hpl.hp.com/personal/Vinay_Deolalikar/ 。

[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

收藏
免费 0
支持
分享
最新回复 (3)
雪    币: 328
活跃值: (34)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2
这是论文。。
上传的附件:
2010-8-11 16:25
0
雪    币: 205
活跃值: (41)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
据说已经有人指出了该证明里的一些问题,作者已经把论文撤了下来。
2010-8-14 11:36
0
雪    币: 67
活跃值: (30)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
关键就看这个错误是否致命了。从作者的回应来看,应该是打算address一下别人提出的问题而已。旧的论文并没有撤下来,还提供了最新的论文:
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf

呃,这个引用,严重影响阅读了。只好手工分一下行,并非“原封不动”的引用。

Source:http://www.hpl.hp.com/personal/Vinay_Deolalikar/
Vinay Deolalikar. P is not equal to NP. 6th August, 2010 (66 pages 10pt, 102 pages 12pt).
Manuscript sent on 6th August to several leading researchers in various areas. You can find an older version here.
Many researchers advised me to prepare a concise synopsis of the proof. I have done so, you may obtain it here.
The 3 issues that were raised were
(a) the use of locality and the techniques used to deal with complex fixed points
(b) the difference between 9-SAT and XORSAT/2-SAT and
(c) clarification on the method of parametrization.
I will address all these in the version being prepared, which
will be sent for peer and journal review.
2010-8-16 02:52
0
游客
登录 | 注册 方可回帖
返回
//