向Vinay Deolalikar证明P！= NP [英] Explain the proof by Vinay Deolalikar that P != NP

问题描述

最近有论文由HP Labs的Vinay Deolalikar游走，声称已证明 P！= NP .

Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP.

有人能解释一下这个证明对我们的影响吗?

Could someone explain how this proof works for us less mathematically inclined people?

推荐答案

我只浏览了这篇论文，但这是它们如何相互融合的粗略总结.

I've only scanned through the paper, but here's a rough summary of how it all hangs together.

摘自论文第86页.

...多项式时间 算法先后成功 将问题分解"为 较小的子问题 通过条件彼此 独立.因此，多项式 时间算法无法解决 政权中的问题 顺序与基础 问题实例需要同时进行 分辨率.

... polynomial time algorithms succeed by successively "breaking up" the problem into smaller subproblems that are joined to each other through conditional independence. Consequently, polynomial time algorithms cannot solve problems in regimes where blocks whose order is the same as the underlying problem instance require simultaneous resolution.

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

Other parts of the paper show that certain NP problems can not be broken up in this manner. Thus NP/= P

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

Much of the paper is spent defining conditional independence and proving these two points.

这篇关于向Vinay Deolalikar证明P！= NP的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！