解释Vinay Deolalikar证明P!= NP的证据

Question

最近在惠普实验室的Vinay Deolalikar周围发表了一篇论文,声称已证明P!= NP.

有人可以解释一下这个证明对我们这个数学上不那么倾向的人有用吗？

Answer 1

我只是通过论文进行了扫描,但这里有一个关于它们如何挂在一起的粗略总结.

从论文的第86页开始.

...多项式时间算法通过连续"分解"问题成为通过条件独立性相互连接的较小子问题而成功.因此,多项式时间算法不能解决其中顺序与底层问题实例相同的块需要同时解决的方案中的问题.

本文的其他部分表明某些NP问题不能以这种方式分解.因此NP/= P.

大部分论文用于定义条件独立性并证明这两点.

Answer 2

迪克利普顿有一篇很好的博客文章,关于这篇论文及其对它的第一印象.不幸的是,它也是技术性的.据我所知,Deolalikar的主要创新似乎是使用统计物理学和有限模型理论中的一些概念,并将它们与问题联系起来.

我和Rex M在一起,有些结果,主要是数学上的结果,不能向缺乏技术掌握的人表达.

Answer 3

我喜欢这个(http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html):

他的论点围绕着一个特定的任务,即布尔可满足性问题,它询问逻辑陈述的集合是否可以同时为真,或者它们是否相互矛盾.这被认为是NP问题.

Deolalikar声称已经证明没有程序可以从头开始快速完成它,因此它不是P问题.他的论点涉及统计物理学的巧妙运用,因为他使用的数学结构遵循许多与随机物理系统相同的规则.

上述效果可能非常显着:

如果结果如此,那将证明P和NP这两个类别不相同,并对计算机可以完成的任务施加严格的限制 - 这意味着许多任务可能从根本上,不可简化地复杂化.

对于某些问题 - 包括因子分解 - 结果并没有明确说明它们是否可以快速解决.但是一个名为"NP-complete"的巨大子问题将注定失败.一个着名的例子是旅行商问题 - 找到一组城市之间的最短路线.可以快速检查这些问题,但如果P？NP然后没有可以从头开始快速完成它们的计算机程序.

Answer 4

这是我对证明技术的理解:他使用一阶逻辑来表征所有多项式时间算法,然后表明对于具有某些属性的大型SAT问题,没有多项式时间算法可以确定它们的可满足性.