第三章：模拟、归约与完备性

计算模型和问题之间的比较依赖可控转换。simulation 比较模型能力，reduction 比较问题困难性；两者都必须记录转换开销。

Simulation

模型 $A$ 模拟模型 $B$，意味着 $B$ 的任意程序都能系统地转换为 $A$ 的程序，并保持输出语义。若 $B$ 程序使用资源 $r(n)$，模拟后的资源可写为

$$r_A(n)\le h(n,r_B(n)).$$

模拟结论必须说明：

• 配置如何编码；
• 一步 $B$ 转移需要多少步 $A$ 操作；
• 编码长度如何增长；
• 随机性、非确定性或 uniformity 是否保持；
• 资源上界在哪个输入长度下计算。

多项式开销模拟可说明 $\mathsf P$ 等类对模型选择稳定，但不能保持 fine-grained exponent。

Many-one reduction

language $A$ 到 $B$ 的多项式时间 many-one reduction 记为

$$A\le_m^p B,$$

若存在多项式时间函数 $f$ 满足

$$x\in A\iff f(x)\in B.$$

$f$ 只调用一次目标问题，并且答案不经额外解释。若 $B\in\mathsf P$，则先计算 $f(x)$ 再判定 $B$，得到 $A\in\mathsf P$。

方向需要严格区分。$A\le B$ 表示 $B$ 至少和 $A$ 一样难；要证明新问题 $B$ 困难，应从已知困难问题 $A$ 归约到 $B$。

Turing reduction

Turing reduction 允许算法把 $B$ 当作 oracle，多次、自适应地查询：

$$A\le_T^p B.$$

它比 many-one reduction 更强。例如从 SAT decision 构造满足赋值会根据前一次回答继续固定变量，属于自适应查询。

归约越强，越容易证明 completeness，但结论越弱。若目标是传递 NP-completeness 的结构性质，通常优先使用 many-one reduction。

Search reduction

search problem 的归约需要把目标问题输出转换回源问题 witness。可写为：

1. instance map：$x\mapsto x'$；
2. solution map：$(x,y')\mapsto y$；
3. 对任意有效 $y'$，输出 $y$ 必须满足源关系；
4. 无解、totality、近似比等性质按需要保持。

优化问题中常用 approximation-preserving reduction。只保持精确最优值的归约未必保持近似质量。

随机归约与分布保持

随机归约允许映射使用随机位，并以规定概率保持答案。平均复杂度中还需控制输出分布；把简单输入映射到目标问题的极端稀有实例，不能说明目标在自然分布下困难。

cryptographic reduction 通常还记录 success probability 与运行时间：

$$\operatorname{Adv}_A(n) \le q(n)\operatorname{Adv}_B(n)+\varepsilon(n).$$

仅有“若能攻击 A 就能攻击 B”的逻辑关系不足以判断安全参数。

Closure 与归约传递

若归约关系可传递，且目标复杂度类对归约前处理封闭，则可以组合困难性结论。例如

$$A\le_m^p B,\quad B\le_m^p C \Longrightarrow A\le_m^p C.$$

组合后仍需检查时间与长度增长。多项式的有限复合仍为多项式，但 fine-grained reduction 的指数损失可能使条件 lower bound 失去意义。

Hardness 与 completeness

给定复杂度类 $\mathcal C$：

• $B$ 是 $\mathcal C$-hard：对所有 $A\in\mathcal C$，有 $A\le B$；
• $B$ 是 $\mathcal C$-complete：$B$ 是 $\mathcal C$-hard 且 $B\in\mathcal C$。

hardness 是 lower-bound transfer：若 $B$ 有高效算法，则整个类都有相应算法。membership 是 upper bound：给出模型中的算法或 verifier。

complete problem 是复杂度类在某种归约下的代表。不同归约可能产生不同 complete 集合，因此完整表述必须包含归约类型。

Reduction 不能自动证明什么

从 $A\le_m^p B$ 可以推出：

• $B\in\mathsf P\Rightarrow A\in\mathsf P$；
• $A\notin\mathsf P\Rightarrow B\notin\mathsf P$；
• 若 $A$ 为 $\mathsf{NP}$-hard，则 $B$ 也为 $\mathsf{NP}$-hard。

但若尚不知道 $A\notin\mathsf P$，归约不会生成无条件 lower bound。SAT 的 NP-completeness 说明 SAT 的多项式时间算法将导致 $\mathsf P=\mathsf{NP}$，不是 SAT 指数 lower bound。

归约设计方法

构造归约时，先确定源实例中需要保留的结构：

• variable gadget 表达局部二元选择；
• consistency gadget 约束多个位置表示同一对象；
• clause/constraint gadget 表达可行性；
• budget 参数阻止不希望的解；
• gap construction 放大 yes/no 实例之间的最优值差异。

证明分为 completeness 与 soundness：

• completeness：源 yes 实例产生目标 yes 实例；
• soundness：目标 yes 解可以恢复源 yes 证据，或源 no 必然映射为目标 no。

只展示映射示例不能代替双向证明和规模分析。

本章自测

1. 模型间多项式模拟为什么不足以保持 $n^{2-o(1)}$ lower bound？
2. 证明问题 $B$ 是 NP-hard 时，归约方向应如何选择？
3. Turing reduction 为什么通常弱于 many-one completeness 结论？
4. search reduction 除实例映射外还必须提供什么？
5. NP-complete 为什么不等于已经证明指数时间下界？

上一章：计算模型 · 下一章：可计算性与不可判定性 →