最近，HP 实验室的 Vinay Deolalikar 发表了一篇论文，声称证明了P != NP。
有人能解释一下这个证明如何适用于我们不太喜欢数学的人吗？
问问题
18150 次
7 回答
57
我只浏览了这篇论文，但这里有一个粗略的总结，说明它们是如何联系在一起的。
从论文的第 86 页开始。
...多项式时间算法通过连续地将问题“分解”成更小的子问题来取得成功，这些子问题通过条件独立性相互连接。因此，多项式时间算法无法解决与底层问题实例顺序相同的块需要同时解决的问题。
论文的其他部分表明，某些 NP 问题不能以这种方式分解。因此 NP/= P
本文的大部分内容都用于定义条件独立性并证明这两点。
于 2010-08-09T03:11:47.343 回答
16
迪克立顿有一篇关于这篇论文和他对它的第一印象的不错的博客文章。不幸的是，它也是技术性的。据我了解，Deolalikar 的主要创新似乎是使用了统计物理学和有限模型理论中的一些概念，并将它们与问题联系起来。
我和 Rex M 一起用这个，有些结果，主要是数学结果，无法向缺乏技术掌握的人表达。
于 2010-08-09T03:42:36.547 回答
9
我喜欢这个（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 则没有计算机程序可以从头开始快速完成它们。
于 2010-08-11T10:27:07.337 回答
5
这是我对证明技术的理解：他使用一阶逻辑来表征所有多项式时间算法，然后表明对于具有某些性质的大型 SAT 问题，没有多项式时间算法可以确定其可满足性。
于 2010-08-09T04:13:43.590 回答
3
另一种思考方式，这可能是完全错误的，但我在第一遍阅读时的第一印象是，我们认为在电路满意度中分配/清除术语是形成和破坏“有序”的集群结构'，然后他使用统计物理学来表明多项式运算的速度不足以在特定的运算“相空间”中执行这些运算，因为这些“簇”最终相距太远。
于 2010-08-09T13:01:36.287 回答
1
这样的证明必须涵盖所有类别的算法，例如连续全局优化。
例如，在3-SAT 问题中，我们必须评估变量以实现这些变量的三元组或其否定的所有替代项。看x OR y可以改成优化
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
类似地，三个变量的替代项有七个项。
为所有项找到此类多项式之和的全局最小值将解决我们的问题。（来源）
它使用梯度方法、局部最小值去除方法、进化算法从标准组合技术转向连续世界。这是完全不同的王国——数值分析——我不相信这样的证明真的能涵盖（？）
于 2010-08-12T09:05:46.257 回答
-4
值得注意的是，有了证明，“魔鬼在细节中”。高级概述显然是这样的：
项目之间的某种关系，表明这种关系意味着 X 并且意味着 Y，因此我的论点得到了展示。
我的意思是，它可能是通过归纳法或任何其他形式的证明，但我要说的是高级概述是无用的。解释它没有意义。虽然这个问题本身与计算机科学有关，但最好留给数学家（认为它肯定非常有趣）。
于 2010-08-09T13:42:13.697 回答