| 查看: 2120 | 回复: 8 | |||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | |||
[交流]
【分享】惠普研究员称已解决计算机科学第一难题 已有8人参与
|
|||
|
转自：http://news.cnblogs.com/n/70425/ 这几天惠普新闻不断。其实技术人员更应该关心的，不是那个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宣布自己摘取了这项桂冠。他已经将论文发给多位各个领域的顶尖专家进行同行评审。目前尚没有得到任何正式的确认。不过，这个问题的提出者、图灵奖得主Stephen Cook评论，（Deolalikar的）“声明看上去比较严肃”。 著名的计算理论博客、佐治亚理工学院计算机科学教授Dick Lipton也发表文章简单解释了论文的思路，认为这项工作是严肃的。Lipton在文中说，Deolalikar是通过有限模型理论搭桥，引出反证，用到了Moshe Vardi (1982)和Neil Immerman (1986)的结论。 8月9日，Lipton又综合已有的对论文的评论，发表了新的文章，认为证明肯定存在错误，但他又表示，这是任何突破性研究都无法避免的。该证明的策略是否证明，存在的问题是否能够修正，仍然有待研究。 此外，犹他大学计算机学院的助理教授Suresh Venkatasubramanian通过Google Docs（链接,可能无法访问）来讨论这一证明，充分利用集体智慧，你也可以加入！文档本身应该是LaTeX格式的。 袁泳在Twitter上分析了Deolalikar的思路，“是通过编码K-SAT构造某种有序结构。如果NP=P，那根据Vardi的定理，K-SAT能用FO(LFP)，也就是最小不动点的一阶逻辑表达，也就说存在某个多项式时间基于LFP的算法。但是该结论同K-SAT的某些统计性质矛盾。”但他也表示自己的知识不足以评价甚至看懂这篇论文。 Vinay Deolalikar是否真的解决了计算机科学界目前的最大问题呢？让我们拭目以待。如果你看懂了这篇论文，请与我们联系。  Vinay Deolalikar，1971年出生于印度新德里，1994年在孟买印度理工学院获得电机工程硕士学位，1999年在南加州大学获得电机工程和数学博士学位。他的研究兴趣是数论、代数几何及其在编码理论中的应用，机器学习与数据挖掘及其在信息管理中的应用，数理逻辑，随机过程，统计学，数字通信等。他在惠普研究院网站上的个人网页是：http://www.hpl.hp.com/personal/Vinay_Deolalikar http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf |
回复此楼» 猜你喜欢
材料与化工调剂
已经有26人回复
-
一志愿211，化学310分，本科重点双非，求调剂
已经有19人回复
-
求调剂288
已经有7人回复
-
298求调剂
已经有13人回复
-
281求调剂
已经有3人回复
-
265求调剂
已经有11人回复
-
301求调剂
已经有5人回复
-
343求调剂
已经有3人回复
-
272分材料子求调剂
已经有18人回复
-
273求调剂
已经有57人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 蛋白纯化
已经有7人回复
- 问个工作职称的翻译问题！在像中科院等这样的 下属研究所里 助理研究员 怎么翻译
已经有9人回复
- HP惠普SimpleSave移动硬盘文件
已经有2人回复
- 惠普微型计算机主机型号：HSTNC-002L-TC怎么用
已经有7人回复
- 求研究员职称证书样式
已经有7人回复
- 中国科学院青岛生物能源与过程研究所模拟仿真团队“百人计划”兰峥岗研究员现公开招聘
已经有3人回复
- 请问北京生命科学研究所助理研究员一个月税前收入多少呀？
已经有6人回复
- 中国科学院生命科学研究院孙中生课题组招聘助理研究员
已经有6人回复
- 【原创】新加坡化学与工程科学研究所(ICES) 招募项目研究员
已经有12人回复
- 【转帖】中国科学院化学研究所韩布兴研究员催化方面的文章发表在最新《science》上
已经有71人回复
7楼2010-08-28 12:32:58
beijiguang6327
铁虫 (小有名气)
- 应助: 0 (幼儿园)
- 金币: 3963
- 帖子: 133
- 在线: 67.5小时
- 虫号: 590110
- 注册: 2008-08-31
- 性别: GG
- 专业: 数论
2楼2010-08-11 09:29:30
4楼2010-08-12 18:09:40
coffee999
金虫 (著名写手)
- 应助: 6 (幼儿园)
- 金币: 3697.7
- 散金: 3247
- 红花: 8
- 帖子: 2331
- 在线: 459.6小时
- 虫号: 443077
- 注册: 2007-10-27
- 专业: 计算机网络
5楼2010-08-13 08:37:13
10