解释Vinay Deolalikar的certificateP！= NP
最近，惠普实验室的Vinay Deolalikar发表了一篇文章 ，声称已经certificateP！= NP 。
有人可以解释一下，这个certificate对我们来说是不是那些有math意义的人呢？
我只是通过论文扫描，但是这里粗略地总结了它们是如何挂在一起的。
从本文的第86页开始。
多项式时间algorithm通过将问题连续地“分解”成通过条件独立性彼此连接的较小子问题而成功。 因此，多项式时间algorithm不能解决其中顺序与基本问题实例相同的块需要同时parsing的情况下的问题。
本文的其他部分表明某些NP问题不能以这种方式分解。 因此NP / = P
大部分的论文都是用来定义条件独立性和certificate这两点的。
迪克·利普顿（Dick Lipton）有关这篇论文的一篇很好的博客文章以及他的第一印象。 不幸的是，这也是技术性的。 据我所知，Deolalikar的主要创新似乎是使用统计物理和有限模型理论中的一些概念，并将其与问题联系起来。
我与雷克斯M这一个，一些结果，主要是math的不能expression给那些谁缺乏技术的掌握。
我喜欢这个（ http://www.newscientist.com/article/dn19287-p-np-its-bad-news-for-the-power-of-computing.html ）：
他的论点围绕着一个特定的任务，布尔可满足性问题，它问一个逻辑陈述的集合是否可以同时为真或是否相互矛盾。 这是已知的NP问题。
Deolalikar声称已经表明，没有可以从头开始快速完成的程序，因此它不是一个P问题。 他的论点涉及统计物理学的巧妙运用，因为他使用的math结构遵循许多与随机物理系统相同的规则。
以上的效果可能相当显着：
如果结果如此，则certificateP和NP这两个类别是不一样的，并且对计算机能够完成的工作施加严格的限制 – 这意味着许多任务可能是根本的，不可复制的。
对于一些问题 – 包括因素分析 – 结果并没有明确说明是否可以很快解决。 但是，一个巨大的“NP完全”问题将会注定要失败。 一个着名的例子是旅行推销员的问题 – find一组城市之间的最短路线。 这样的问题可以快速检查，但是如果P≠NP，那么就没有可以从头开始快速完成的计算机程序。
这是我对certificate技术的理解：他使用一阶逻辑来表征所有多项式时间algorithm，然后表明对于具有某些性质的大SAT问题，没有多项式时间algorithm可以确定它们的可满足性。
另一种思考方式，可能是完全错误的，但是我第一遍读到它的第一印象是，我们认为在电路满意度中分配/清除条件是形成和打破“有序”结构“，然后他使用统计物理学来表明，在多项式运算中没有足够的速度在操作的特定”阶段空间“中执行这些操作，因为这些”簇“最终分离得太远了。
这样的certificate将不得不涵盖所有类别的algorithm，如连续的全局优化 。
例如，在3-SAT问题中，我们必须评估variables，以满足这些variables的三元组或其否定的所有替代scheme。 看看x OR y可以变成优化
((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)
并类推七个术语来替代三个variables。
find所有项的这种多项式和的全局最小值将解决我们的问题。 （ 来源 ）
它将采用标准的组合技术，用连续世界的梯度方法，局部极小值去除方法，演化algorithm。 这是完全不同的王国 – 数值分析 – 我不相信这样的certificate可以真正覆盖（？）
值得注意的是，有了证据，“魔鬼就是细节”。 高层次的概述显然是这样的：
项目之间的某种关系表明，这种关系暗示着X，暗示着Y，因此我的论证被显示出来。
我的意思是，它可能是通过感应或任何其他forms的certificate的东西，但我所说的是高层次的概述是无用的。 没有必要解释它。 虽然这个问题本身与计算机科学有关，但math家最好留给他们（这个想法肯定是令人难以置信的）。
