新书推介:《语义网技术体系》
作者:瞿裕忠,胡伟,程龚
   XML论坛     >>W3CHINA.ORG讨论区<<     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
  •   Add to Google

    >> 谈谈如何做研究,谈谈自己的科研生活
    [返回] W3CHINA.ORG讨论区 - 语义网·描述逻辑·本体·RDF·OWL休息区『 科研生涯 』 → 惠普研究员称已解决计算机科学第一难题:证明 P != NP 查看新帖用户列表

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 22789 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子 浏览下一篇主题
     * 贴子主题: 惠普研究员称已解决计算机科学第一难题:证明 P != NP 举报  打印  推荐  IE收藏夹 
       本主题类别: 科研生涯    
     admin 帅哥哟,离线,有人找我吗?
      
      
      
      威望:9
      头衔:W3China站长
      等级:计算机硕士学位(管理员)
      文章:5255
      积分:18406
      门派:W3CHINA.ORG
      注册:2003/10/5

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    兴趣:
    * XML相关技术
    * 资料收集
    * Ontology Engineering
    * Web架构
    * SW Implementation
    给admin发送一个短消息 把admin加入好友 查看admin的个人资料 搜索admin在『 科研生涯 』 的所有贴子 点击这里发送电邮给admin  访问admin的主页 引用回复这个贴子 回复这个贴子 查看admin的博客楼主
    发贴心情 惠普研究员称已解决计算机科学第一难题:证明 P != NP

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

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

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

    现在,Vinay Deolalikar宣布自己摘取了这项桂冠。他已经将论文发给多位各个领域的顶尖专家进行同行评审。目前尚没有得到任何正式的确认。不过,这个问题的提出者、图灵奖得主[URL=http://zh.wikipedia.org/zh-cn/%E5%8F%B2%E6%8F%90%E8%8A%AC%C2%B7%E5%8F%A4%E5%85%8B]Stephen Cook[/URL]评论,(Deolalikar的)“声明看上去比较严肃”

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

    著名的计算理论博客、佐治亚理工学院计算机科学教授Dick Lipton也发表[URL=http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/]文章[/URL]简单解释了论文的思路,认为这项工作是严肃的。Lipton在文中说,Deolalikar是通过有限模型理论搭桥,引出反证,用到了Moshe Vardi (1982) 和Neil Immerman (1986)的结论。

    8月9日,Lipton又综合已有的对论文的评论,发表了新的[URL=http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/]文章[/URL],认为证明肯定存在错误,但他又表示,这是任何突破性研究都无法避免的。该证明的策略是否证明,存在的问题是否能够修正,仍然有待研究。

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

    CSDN博客专家[URL=http://blog.csdn.net/g9yuayon]袁泳[/URL]在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/ 。

    转自:http://news.csdn.net/a/20100810/277993.html


       收藏   分享  
    顶(0)
      




    ----------------------------------------------

    -----------------------------------------------

    第十二章第一节《用ROR创建面向资源的服务》
    第十二章第二节《用Restlet创建面向资源的服务》
    第三章《REST式服务有什么不同》
    InfoQ SOA首席编辑胡键评《RESTful Web Services中文版》
    [InfoQ文章]解答有关REST的十点疑惑

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2010/8/10 12:07:00
     
     willnow 帅哥哟,离线,有人找我吗?
      
      
      等级:大一新生
      文章:8
      积分:81
      门派:XML.ORG.CN
      注册:2010/4/17

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给willnow发送一个短消息 把willnow加入好友 查看willnow的个人资料 搜索willnow在『 科研生涯 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看willnow的博客2
    发贴心情 
    飘过
    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2010/8/10 13:06:00
     
     GoogleAdSense
      
      
      等级:大一新生
      文章:1
      积分:50
      门派:无门无派
      院校:未填写
      注册:2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 科研生涯 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/3/28 8:16:48

    本主题贴数2,分页: [1]

    管理选项修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    46.875ms