形式陈述

语言 $A\subseteq\Sigma^*$$A\subseteq {\mathrm{\Sigma }}^{\ast }$ 多项式时间 many-one 归约到 $B\subseteq\Gamma^*$$B\subseteq {\mathrm{\Gamma }}^{\ast }$，记 $A\le_m^p B$$A{\le }_m^{p}B$，若存在多项式时间可计算的全函数 $f:\Sigma^*\to\Gamma^*$$f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$，使

$$ \forall x\in\Sigma^*\quad x\in A\Longleftrightarrow f(x)\in B. $$$$\mathrm{\forall }x\in {\mathrm{\Sigma }}^{\ast }x\in A⟺f(x)\in B.$$

双向成员条件与统一的高效变换缺一不可。

直觉

归约把每个 $A$$A$ 实例一次性翻译成 $B$$B$ 实例并严格保留是/否答案；高效解决 $B$$B$ 因而会高效解决 $A$$A$。

例子与边界

证明 $B$$B$ 为 NP-hard 时，应从已知困难问题 $A$$A$ 归约到 $B$$B$，方向反过来不能建立所需困难性。只证明是实例映成是实例而不保证否实例，会失去判定等价。

推论与应用

多项式时间归约组织 NP 完全性理论并比较问题难度。Turing 归约允许多次自适应询问，是不同且通常更强的概念。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, Chs. 1–8。
• Richard M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, 1972, pp. 85–103, Full chapter。