映射归约

映射归约把每个原问题实例一次性翻译成目标问题实例，并要求翻译完整而严格地保存“是/否”答案。它像编译器：源问题的求解可以先编译，再把目标问题求解器作为子程序；因此“目标容易”会推出“源也容易”，而“源很难”可反向证明目标不可能更容易。归约方向最容易写反：要证明 $B$ 困难，应从已知困难的 $A$ 构造 $A{\le }_{m}B$。

证明 $B$ 不可判定时，应从已知不可判定的 $A$ 构造 $A{\le }_{m}B$，而不是反向。$f$ 必须是对所有输入都停机的可计算全函数，且同时保持成员与非成员；只把“是”实例送到“是”实例通常不够，也不能“运行源问题直到知道答案再决定输出什么”，否则便是循环论证。

从 $A_{TM}$ 归约到 $HAL{T}_{TM}$ 时，可把 $⟨M,w⟩$ 映为一台新机器 $N$ 与固定输入：$N$ 模拟 $M(w)$，仅在 $M$ 接受时停机。于是原实例被接受当且仅当新实例属于停机语言。若目标语言有判定器，复合 $f$ 与该判定器就能判定源语言。

映射归约只产生一个目标实例，比允许自适应地多次询问预言机的Turing 归约公理库Turing 归约Turing reduction · Oracle reduction允许算法把目标语言作为预言机进行多次自适应查询的可计算性归约。更受限；两者保存的性质和能够传递的困难性结论不能随意互换。

可计算函数公理库可计算函数Computable function · Recursive function有图灵机对每个合法输入都停机并输出其值的全函数。 提供映射归约中翻译器的形式基础，可判定性公理库可判定语言Decidability · Recursive language · Decidable language存在对所有输入都停机并正确回答成员资格的图灵机语言类。 与 可识别性公理库可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。 可沿归约方向传递；特别地，若 $A{\le }_{m}B$ 且 $B$ 可识别，则 $A$ 可识别。可计算性理论用这一结构统一组织停机问题、Rice 定理和 Post 对应问题之间的不可判定性谱系；复杂度理论则把翻译进一步限制为多项式时间，得到 多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。，用于 NP 完全性等证明。