映射归约

定义也可写成 $A=f^{-1}(B)$。它要求每个输入都先得到一个目标字，却不要求不同输入得到不同字，也不要求覆盖 $B$ 的全部元素。“多一”允许许多源实例共用一个目标实例；归约保存的是成员资格，不是对象的全部结构。

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

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

从 $A_{TM}$ 归约到 $HAL{T}_{TM}$ 时，把 $⟨M,w⟩$ 映为 $⟨N,\epsilon ⟩$：$N$ 忽略自身输入，模拟 $M(w)$；$M$ 接受时停机，$M$ 拒绝时主动进入无限循环，$M$ 原本循环时继续模拟。三种情形中恰好只有接受情形使 $N$ 停机，故两个成员条件等价。

由参数化定理公理库s-m-n 定理s-m-n theorem · Parameter theorem把程序的部分输入有效固化为新程序索引的参数化定理。，生成 $N$ 的编码只需把 $M$ 与 $w$ 写进一段固定程序模板，不运行 $M(w)$，因此即使 $M(w)$ 永不停止，翻译器 $f$ 仍会结束。无效源编码可以统一映到一台永不停止机器的编码，从而覆盖定义要求的全部输入。构造程序和执行程序是不同阶段，这也是许多不可判定性归约得以总可计算的原因。

每个映射归约都是Turing 归约公理库Turing 归约Turing reduction · Oracle reduction允许算法把目标语言作为预言机进行多次自适应查询的可计算性归约。的特殊情形：先计算唯一查询 $f(x)$，再原样返回预言机的成员位。反向不成立。设 $K$ 是停机集，则 $\bar{K}{\le }_{T}K$ 只需翻转一次回答；若有 $\bar{K}{\le }_{m}K$，$K$ 的可识别性便会沿总可计算原像传给 $\bar{K}$，使两边同时可识别而得到停机判定器，矛盾。区别不仅在查询次数，也在能否否定或组合目标答案。

可计算函数公理库可计算函数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 完全性等证明。

Borel 归约公理库Borel 可归约性Borel reducibility用双向保持等价关系的 Borel 编码比较分类问题，手算整数差分类并区分归约、同态和光滑性。保留“用一种分类解决另一种分类”的方向，但对象变成标准 Borel 空间上的等价关系，映射只要求 Borel 可测并双向保持等价。它不带运行时间保证，且不能把仅保留正向等价的同态当成完整归约。