Tide反对数百万美元的数学证明

2017-04-22 13:01:04

雅各布·阿隆(Jacob Aron)最初被誉为计算机科学中最大问题的解决方案,证明P≠NP的​​最新尝试 - 也称为“P vs NP”问题 - 似乎遇到了麻烦两位着名的计算机科学家在加利福尼亚州帕洛阿尔托的惠普实验室的Vinay Deolalikar的证据草案中指出了潜在的“致命缺陷”自从一周前100页的证据爆炸到互联网上以来,数学家和计算机科学家一直在竞相理解它问题涉及计算机完成任务的速度,例如将数字分解粗略地说,P是可以快速计算的一组问题,而NP包含可以快速检查答案的问题通常怀疑P≠NP如果是这样的话,它会严重限制计算机可以完成的任务 Deolalikar声称证明了这一点如果他证明是正确的,他将从马萨诸塞州剑桥的克莱数学研究所获得100万美元的千禧奖关于证据的激动人心的在线讨论大多发生在佐治亚理工学院计算机科学家Richard Lipton的博客上,他在P vs NP上工作了30多年然而,今天早上,Lipton发布了另一位计算机科学家,马萨诸塞大学的Neil Immerman的电子邮件,他声称在Deolalikar的论文中发现了一个“严重漏洞” Immerman的关键点与他所说的Deolalikar假设中的错误有关,同时试图以特定的方式描述P的集合 Deolalikar试图通过调用另一个称为FO(LFP)的数学集来证明某些问题在NP中而在P中没有(因此P≠NP) Immerman说,鉴于在证明中部署的其他方法,这个集合不能以这种方式使用与所有着名的未解决的数学问题一样,处理P对NP的尝试很常见但很少被认真对待,因为它们往往缺乏强大的理论基础 Deolalikar的证据似乎是由于他在惠普实验室担任研究员的专业地位,以及多伦多大学的Stephen Cook的评论,他最初制定了P vs NP问题,并指出Deolalikar的工作似乎构成了一个“相对严重的主张”本周早些时候,加利福尼亚大学洛杉矶分校的Terence Tao在评论Lipton的博客时,将证明正确性的问题分解为三种情景在最好的情况下,小调整将修复Deolalikar的论点,并一劳永逸地证明P≠NP或者,大修可能最终挽救证据如果做不到这一点,Deolalikar的一般证据策略可以为未来的证据尝试提供希望陶然后写道,他认为前两种情况不太可能,但第三种情况仍未得到解决在回应伊梅尔曼今天的批评时,他将评估修改为“否”,“否”和“可能不是”即使这些批评立场,整个事件仍可能间接地激发数学发现在Deolalikar声称之后,建立了一个wiki,人们可以就Deolalikar的证据发表意见评论范围从小错别字的更正到他的方法的详细数学批评这一系列的在线活动表明,一种新的数学方式可能正在出现,博客和维基可以与黑板和期刊相媲美 - 这可能是一个积极的结果,即使P vs NP仍未得到解决剑桥大学的Timothy Gowers说: