多项式时间归约

可以把 $f$ 看成一个不知答案的编译器。它把源实例改写成目标实例，目标的一个是/否位可以原样解释回源问题。若目标有快速判定器，就把“编译器 + 目标判定器”串联起来解决源问题；若源已经代表一族困难问题，箭头所指的目标便至少承载同样的困难性。

双向等价承担了归约的正确性。只把是实例送到是实例，会允许否实例随意落入目标语言，目标答案便不能可靠解释；只画出两个问题在外观上的相似，也没有构成算法变换。

独立集到顶点覆盖 ​

定义

对含 $n$ 个顶点的良构输入，令

集合 $S\subseteq V$ 独立，当且仅当 $V\setminus S$ 覆盖每条边，因此

例如在三角形 $K_3$ 中，$k=1$ 映成覆盖阈值 $2$，两边都为是实例；$k=2$ 映成阈值 $1$，两边都为否实例。变换只复制图并计算 $n-k$，规模与时间均为输入长度的多项式。若约定非法编码不属于源语言，归约就应把非法编码或越界阈值统一映到一个固定的 VC 否实例，才能成为定义要求的全函数。

方向与接口边界 ​

要把已知困难语言 $A$ 的困难性传给 $B$，方向必须是 $A{\le }_m^{p}B$。反向 $B{\le }_m^{p}A$ 只说明可用 $A$ 的算法解决 $B$。证明还必须覆盖“源是则目标是”和“目标是则源是”，且构造 $f$ 时不能调用目标判定器。

本页只定义判定语言间的一次 Karp 归约。Turing 归约允许多次、可自适应地询问目标 oracle，通常更强。

L-reduction公理库L-reductionL-reduction · Linear reduction以两个常数同时控制目标最优值尺度和解误差回传，从而保持常数近似性的优化归约。控制优化值与误差，gap reduction公理库Gap 问题与 gap reductionGap problem · Gap reduction · Gap-preserving reduction以带承诺的最优值阈值间隙和保持两端阈值的归约，把局部检验可靠性转化为不可近似性。保存承诺间隙，FPT 归约公理库FPT 归约FPT reduction · Parameterized reduction在 f(k)|x|^{O(1)} 时间内保持答案，并把目标参数限制为原参数函数的参数化 many-one 归约。还约束新参数。普通 Karp 归约不会自动传递这些额外结构，也不会自动保留通信量、查询次数或学习成功概率。

若 $A{\le }_m^{p}B$ 且 $B\in \mathbf{P}$，先算 $f(x)$ 再运行 $B$ 的判定器，得到 $A\in \mathbf{P}$。

若 $B\in \mathbf{NP}$，目标证书长度是 $|f(x)|$ 的多项式，而 $|f(x)|$ 又是 $|x|$ 的多项式，所以同样有 $A\in \mathbf{NP}$。这种“容易性沿箭头反向传播”的性质，是NP 困难性公理库NP 困难性NP-hardnessNP 中每个语言都可多项式时间归约到目标问题。与NP 完全性公理库NP 完全性NP-completeness同时属于 NP 且为 NP-hard 的性质。的逻辑基础。

相较于可计算性中的映射归约公理库映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。，本页额外限制变换时间与输出长度。选用哪种归约会改变可传递的结论，因此困难性陈述必须连同归约类型书写。