P对NP问题

P对NP问题探讨的是，所有能够被快速验证的解决方案的问题是否也能被快速解决，这是理论计算机科学的核心开放性问题，也是克莱数学千禧年大奖问题之一。

Definition

P是可以在多项式时间内解决的问题的类别，而NP是其提出的解决方案可以在多项式时间内验证的问题的类别；P对NP问题探讨的是这两个类别是否相等，当且仅当某个NP完全问题可以在多项式时间内解决时，它们才相等。

Scope

本主题涵盖了P对NP问题的正式陈述、其与任何NP完全问题是否存在多项式时间算法的等价性、两种答案各自的后果、阻碍进展的障碍（如相对化、自然证明和代数化），以及普遍认为这两类问题不同的猜想。

Core questions

• 找到解决方案是否比检查解决方案本质上更难？
• 为什么答案取决于任何一个NP完全问题是否属于P？
• 如果P等于NP，世界会是什么样子？如果P不等于NP，又会是什么样子？
• 为什么几十年的努力未能解决这个问题？

Key theories

与NP完全性的等价性

P等于NP当且仅当任何NP完全问题都存在多项式时间算法，因此这个宏大的问题可以简化为单个具体问题（如可满足性问题）的可处理性。

证明障碍

相对化、自然证明和代数化结果表明，目前主要的证明技术无法解决P对NP问题，这解释了其难度，并指导着对全新方法的探索。

Clinical relevance

P和NP被假定不相等是处理NP难问题为难解问题以及密码学安全性的基础工作假设，因为有效解决NP问题将破解广泛使用的加密；如果P等于NP的建设性证明得以实现，将彻底改变优化、物流和科学领域。

History

库克于1971年提出了这个问题，并将其与NP完全性联系起来，很快就被认为是基础性问题。20世纪80年代通过电路下界进行的尝试遇到了由拉兹博罗夫和鲁迪奇发现的自然证明障碍，2000年克莱数学研究所将其列为千禧年大奖问题，并设立了100万美元的奖金。

Debates

P对NP问题是否会得到解决，答案是什么？

大多数研究人员推测P不等于NP，但尚无证明，且已知技术被证明不足以解决。关于问题是否即将解决、是否需要全新的数学方法，甚至问题是否可能独立于标准公理，存在不同意见。

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

如果P等于NP会发生什么？

许多目前被认为难以处理的问题，从优化调度到破解加密代码，都将拥有高效的算法，找到解决方案的行为将不比检查它们更难。这将对商业、安全和科学产生深远影响，这也是大多数专家预计P不等于NP的部分原因。

为什么这个问题如此难以解决？

证明P等于NP需要为NP完全问题找到一个快速算法，而目前没有人找到；证明它们不同则需要证明不存在这样的算法。关于相对化和自然证明的结果表明，标准技术本身无法确立后者，因此需要一种全新的方法。