多一归约(Many-One Reduction)

多一归约(Many-One Reduction)又称映射归约,是比较两个判定问题难度的核心技术。它用一个可计算函数,把问题 A 的每个实例映射为问题 B 的一个实例,并保证原实例的答案为是当且仅当映射后的实例答案为是。若存在这样的归约,就记作 A 可多一归约到 B。

概述

多一归约的直觉是:如果能高效地把 A 的问题翻译成 B 的问题,那么只要能解决 B,就能解决 A。因此 B 至少和 A 一样难。在可计算性理论中,归约用于传递不可判定性:若 A 不可判定且能归约到 B,则 B 也不可判定。在复杂度理论中,常要求映射函数在多项式时间内计算,称为多项式时间多一归约,亦称卡普归约,用于定义 NP 完全性。

核心原理

• 保持答案:映射必须让是的实例映到是的实例,否的映到否的实例。
• 方向即难度:A 归约到 B 意味着 B 不比 A 容易。
• 传递难度:用于证明目标问题不可判定或 NP 完全。
• 资源受限:根据场景,映射函数被限定为可计算、多项式时间或对数空间。

应用场景

多一归约是证明不可判定性和完全性的标准工具。证明停机问题的众多变体不可判定,以及证明大量组合问题 NP 完全,都依赖于构造合适的归约。它把复杂的下界证明,转化为设计一个保持答案的映射,使难度分析变得结构化、可复用。

常见问题

问:多一归约和图灵归约有何不同?答:多一归约只调用目标问题一次并直接返回其答案;图灵归约允许把目标问题当作可多次调用的子程序,更为一般。

问:归约方向为什么容易搞反?答:证明 B 难时,要把已知难的 A 归约到 B,而不是反过来;方向错了会得出无意义的结论。