解释 Vinay Deolalikar 的证明 P != NP [已关闭]

Question

最近有一个 纸 惠普实验室的 Vinay Deolalikar 声称已经证明了这一点 P!=NP.

有人能解释一下这个证明对于我们数学不太擅长的人来说是如何工作的吗？

Answer 1

我只透过纸张扫描，但这里的所有挂起如何在一起。

这是一个粗略的总结

从纸的86页。

  

...多项式时间   算法通过连续成功   “分手”的问题进入   在加入到更小的子问题   对方通过条件   独立。因此，多项式   时间的算法解决不了   在制度的问题，其中的块，其   顺序是一样的底层   问题实例需要同时   分辨率。

的纸显示其它部分，某些NP问题不能以这种方式破碎。因此NP / = P

大部分纸的是花限定条件独立性和证明这两点。

Answer 2

迪克·利普顿有一个很好的博客条目有关纸张和他的这第一印象。不幸的是，它也是技术。从我能理解，Deolalikar的主要创新似乎是使用从统计物理和有限元模型理论的一些概念，并配合他们的问题。

我和雷克斯米，这其中，一些成果，主要是数学的人不能表达给谁缺乏技术精通的人。

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完整”。一个著名的例子是旅行推销员问题 - 找到一组城市之间的最短路线。可以快速检查此类问题，但是如果P≠NP，则没有计算机程序可以从头开始快速完成它们。

Answer 4

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

Answer 5

想着它，这可能是完全错误的，而且是我读它在第一轮我的第一印象的另一种方式，就是我们认为分配/作为形成和断裂集群电路满意结算条款的“有序结构”，而他则利用统计物理学表明没有足够的速度在多项式操作中的特定操作“相空间”执行这些操作，因为这些“群”最终会被太远开。

Answer 6

这样的证明将必须覆盖的算法的所有类，如连续全局优化

例如，在 3-SAT问题的我们要评估的变量来满足这些变量或者他们否定的三元组的所有可选方案。外观，x OR y可以变成优化

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

和用于三个变量的替代类似7条款。

找到这样的多项式的总和的全球最小的所有条款会解决我们的问题。 （源）

这将标准组合技术与连续世界using_gradient方法，本地量滴除去方法，进化算法进行。这是完全不同的国度 - 数值分析 - 我不相信这样的证据可能真的盖

（？）

Answer 7

值得注意的是与校样，“魔鬼在细节”。的高级概述显然是这样的：

  

一些某种关系的   项目之间，表明该   关系意味着X和   意味着Y和由此我的观点是   所示。

我的意思是，它可以是经由感应或证明的东西的任何其它形式的，但我说的是高层次的概述是没用的。没有一点解释它。虽然这个问题本身涉及计算机科学，最好是留给数学家（认为它肯定是非常有趣）。