Vinay Deolalikar的证明说明P与NP不相等。
1
我只是粗略地浏览了论文，以下是它们之间的大体联系的简要总结。
来自论文的第86页。
……通过将问题连续“分解”成相互通过条件独立性连接在一起的更小的子问题，多项式时间算法成功地解决了问题。因此，多项式时间算法无法解决需要同时解决具有与基础问题实例相同顺序的块的问题范围。
论文的其他部分表明了某些NP问题不能以这种方式分解。
因此，NP ≠ P。
论文的大部分内容都花费在定义条件独立性和证明这两个观点上。
Dick Lipton写了一篇不错的博客文章，介绍了这篇论文并分享了他的第一印象。不幸的是，它也很技术化。从我能理解的来看，Deolalikar的主要创新似乎是使用了一些统计物理学和有限模型理论的概念，并将它们与问题联系起来。
我和Rex M的想法一样，在某些结果上，尤其是大多数数学结果，无法向缺乏技术基础的人解释清楚。
我喜欢这篇文章（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，则没有计算机程序可以从头快速完成它们。
1
1
另一种思考方式，可能完全错误，但这是我第一次阅读时的第一印象，我们认为在电路满足中分配/清除术语形成和破坏“有序结构”的聚类，然后他使用统计物理学表明，在特定的操作“相空间”中，多项式运算速度不足以执行这些操作，因为这些“聚类”最终距离太远。
1
这样的证明必须涵盖所有类别的算法，例如连续全局优化。
例如，在3-SAT问题中，我们必须评估变量以满足这些变量或其否定的三元组的所有替代方案。注意，x OR y可以转换为优化。
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
还有三个变量的替代方案，类似地有七个术语。
找到所有术语的多项式和的全局最小值将解决我们的问题。(source)
使用梯度方法、去除局部极小值方法、进化算法等技术，将组合技术引入连续领域，这是完全不同的数值分析领域，我不认为这样的证明能够真正涵盖。
4
某种关系 显示这种关系意味着X，而 意味着Y，因此我的论点被证明。
我的意思是，可能是通过归纳法（Induction）或任何其他形式的证明，但我要说的是高层次概述是无用的。解释它没有意义。尽管问题本身涉及计算机科学，但最好让数学家来解决它（虽然它肯定非常有趣）。
1
原文链接