跳到主要内容

NP 完全复杂度类

阐述​

称一个问题 B 是 NP 完全的，如果

  1. 它属于 NP 复杂度类
  2. 所有 NP 中的 A 都能多项式时间归约为 B。

对于任何 NP 完全问题，如果它在 P 复杂度类中，那么 P 将与 NP 复杂度类相等。

证明​

如果 BB 是 NP 完全的且 B≤PCB\le_P C 对于某个 C∈NPC\in NP，则 CC 是 NP 完全的。

我们经常将 3-SAT 归约为某个语言来证明它是 NP 完全的。在这样做时，我们需要找到这种语言中能模拟变量和分句的结构，这种结构称为「小装置」。

实例​

性质​

相关内容​

参考文献​