多项式时间归约

概述

多项式时间归约是比较问题计算复杂度的核心工具：如果问题 A 可以多项式时间归约到问题 B（记作 A ≤ₚ B），那么 B 至少和 A 一样难。

多项式时间多一归约（Karp 归约）：存在一个多项式时间可计算的函数 f，使得对所有输入 x，x ∈ A 当且仅当 f(x) ∈ B。

Cook 归约（多项式时间图灵归约）：存在一个多项式时间的确定性图灵机，该机器可以访问一个 B 的"神谕"（oracle），并利用这个神谕来解决 A。

传递性：如果 A ≤ₚ B 且 B ≤ₚ C，则 A ≤ₚ C。这使得 NP 完全性证明可以"链式传递"——一旦知道 SAT 是 NP 完全的，只需把 SAT 归约到一个新问题，就能证明新问题也是 NP 完全的。

NP 完全性的定义依赖归约：一个问题 L 是 NP 完全的，如果 NP 中所有问题都可以多项式时间归约到 L。

Richard Karp（1972）通过一系列归约证明了21个经典组合问题都是 NP 完全的，展示了归约作为工具的强大威力。

归约使得研究者可以通过"只需证明一个归约"来建立新问题的 NP 完全性，而无需从头开始分析每个问题的复杂度。这极大地提高了算法研究的效率。