形式陈述

对语言 $A\subseteq\Sigma^*$$A\subseteq {\mathrm{\Sigma }}^{\ast }$、$B\subseteq\Gamma^*$$B\subseteq {\mathrm{\Gamma }}^{\ast }$，若存在全函数 $f:\Sigma^*\to\Gamma^*$$f:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Gamma }}^{\ast }$，且 $f$$f$ 可计算并满足

$$ \forall x,\qquad x\in A\iff f(x)\in B, $$$$\mathrm{\forall }x,x\in A⟺f(x)\in B,$$

则称 $A$$A$ 映射归约或多一归约到 $B$$B$，记作 $A\le_m B$$A{\le }_{m}B$。该关系可传递。若 $A\le_m B$$A{\le }_{m}B$ 且 $B$$B$ 可判定，则 $A$$A$ 可判定；取逆否命题，若 $A$$A$ 不可判定，则 $B$$B$ 不可判定。方向不能反用。

直觉

归约函数把每个原问题实例一次性翻译成目标问题实例，并完整保持“是/否”答案；目标问题的求解器因此可以作为原问题的子程序。

例子与边界

证明 $B$$B$ 不可判定时，应从已知不可判定的 $A$$A$ 构造 $A\le_m B$$A{\le }_{m}B$，而不是反向。$f$$f$ 必须对所有输入停机，且同时保持成员与非成员；只把“是”实例送到“是”实例通常不够。映射归约比允许多次自适应查询的 Turing 归约更强，因此不可随意互换两者结论。

推论与应用

映射归约统一组织不可判定性和完全性证明：停机问题、Rice 定理、Post 对应问题以及 NP 完全性都依赖保持答案的实例变换。它还保持可识别性向上：若 $A\le_m B$$A{\le }_{m}B$ 且 $B$$B$ 可识别，则 $A$$A$ 可识别。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 5 and 7, mapping reducibility and reductions。
• Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987，Chs. 5–8, many-one reducibility and effective transformations。