NP完全性与归约

NP完全问题是NP复杂度类中最难的问题之一，因为每个NP问题都可以有效地归约到它，所以如果能快速解决任何一个NP完全问题，就意味着所有NP问题都能被解决。

Definition

如果一个问题属于NP类，并且NP类中的每个问题都可以通过多项式时间归约归约到它，那么该问题就是NP完全问题；这类问题是NP类中难度最大的成员，通过高效转换彼此等价。

Scope

本主题涵盖了可在多项式时间内验证的问题的NP类、多项式时间多一归约、确立可满足性为NP完全问题的库克-莱文定理、卡普的NP完全组合问题目录，以及通过从已知问题归约来证明新问题是NP完全问题的方法。

Core questions

• 一个问题属于NP类中最难的问题之一意味着什么？
• 库克-莱文定理如何确定第一个NP完全问题？
• 归约如何用于证明一个新问题是NP完全的？
• 为什么一个问题的NP完全性会对成千上万的其他问题产生影响？

Key theories

库克-莱文定理

布尔可满足性是NP完全的，因为任何多项式时间验证器的计算都可以编码为可满足性实例，从而提供了其他问题由此派生的基础完全问题。

卡普归约与NP完全问题网络

卡普通过多项式时间归约证明了21个自然问题，从图着色到旅行商决策问题，都是NP完全的，从而开启了通过不断增长的归约网络来确立问题难度的方法。

Clinical relevance

NP完全性是判断问题难解性的实用诊断方法：一旦调度、物流、设计或验证中的某个问题被证明是NP完全的，工程师就会停止寻求保证快速的精确算法，转而采用近似算法、启发式方法、整数规划求解器或使问题变得可处理的限制条件。

History

库克于1971年证明了可满足性是NP完全的，莱文在苏联独立获得了等效结果。1972年，卡普展示了另外21个NP完全问题，揭示了这种现象的普遍性，并使NP完全性成为诊断计算难度核心工具。

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

NP代表什么？

NP代表非确定性多项式时间。同样地，如果一个问题的候选解可以在多项式时间内被检查，即使找到它看起来很难，那么这个问题就属于NP。给定旅行商路线后，验证其长度是否低于给定值很容易，但发现这条路线本身却似乎很难。

如何证明一个新问题是NP完全的？

你需要证明两点：该问题属于NP类，即候选解可以快速检查；以及某个已知的NP完全问题可以在多项式时间内归约到它。这种归约将已知的难度转移，使新问题成为NP类中最难的问题之一。