多项式时间归约 | Codeboy's Blog

形式陈述

令 $A\subseteq\Sigma^*$ 与 $B\subseteq\Gamma^*$ 是两个判定语言。若存在全函数 $f:\Sigma^*\to\Gamma^*$ 和多项式 $p$ ，使某台确定性机器在 $p(|x|)$ 步内输出 $f(x)$ ，并且

\forall x\in\Sigma^*:\qquad x\in A\iff f(x)\in B,

就称 $A$ 多项式时间 many-one 归约到 $B$ ，记为

A\le_m^p B.

这是一次性映射：归约算法先完整产生一个 $B$ 实例，不能询问 $B$ 的答案再决定输出。因为每写出一个输出符号至少需要一步，多项式时间还自动保证 $|f(x)|\le p(|x|)$ ，排除了指数长度的翻译。

以下的多项式上界都取为非减形式，例如 $C(n+1)^k$ ，其中 $C>0$ 、 $k$ 为非负整数；任意多项式时间上界都可放大为这种形式，不改变资源限制。

归约具有传递性。若 $A\le_m^p B$ 由 $f$ 见证， $B\le_m^p C$ 由 $g$ 见证，则 $h=g\circ f$ 保持成员资格。设计算 $f$ 的时间和输出长度均由 $p(n)$ 控制，计算 $g$ 在长度 $m$ 上耗时 $q(m)$ ，那么

T_h(n)\le p(n)+q(p(n)),

仍是多项式。这一复合计算是归约链能够传递困难性的理由。

直觉

可以把 $f$ 看成一个不知答案的编译器。它把源实例改写成目标实例，目标的一个是/否位可以原样解释回源问题。若目标有快速判定器，就把“编译器 + 目标判定器”串联起来解决源问题；若源已经代表一族困难问题，箭头所指的目标便至少承载同样的困难性。

双向等价承担了归约的正确性。只把是实例送到是实例，会允许否实例随意落入目标语言，目标答案便不能可靠解释；只画出两个问题在外观上的相似，也没有构成算法变换。

例子与边界

独立集到顶点覆盖

定义

\begin{aligned} \mathrm{IS}&=\{\langle G,k\rangle:G\text{ 有大小至少 }k\text{ 的独立集}\},\\ \mathrm{VC}&=\{\langle G,\ell\rangle:G\text{ 有大小至多 }\ell\text{ 的顶点覆盖}\}. \end{aligned}

对含 $n$ 个顶点的良构输入，令

f(\langle G,k\rangle)=\langle G,n-k\rangle.

集合 $S\subseteq V$ 独立，当且仅当 $V\setminus S$ 覆盖每条边，因此

\langle G,k\rangle\in\mathrm{IS} \iff f(\langle G,k\rangle)\in\mathrm{VC}.

例如在三角形 $K_3$ 中， $k=1$ 映成覆盖阈值 $2$ ，两边都为是实例； $k=2$ 映成阈值 $1$ ，两边都为否实例。变换只复制图并计算 $n-k$ ，规模与时间均为输入长度的多项式。若把阈值限制为 $0\le k\le n$ 的合法编码，归约应把其他串映到一个固定的 VC 否实例，才能成为全函数。若语言本来允许任意整数阈值，则不能把越界值一律拒绝： $k\le0$ 是源是实例，应映到固定是实例； $k>n$ 才是源否实例。编码的语法合法性与数学上答案为否是两件事。

同一五边形图中的独立集取补后成为顶点覆盖，阈值从 k 变为 n 减 k — 独立集到顶点覆盖的多项式时间归约

方向与接口边界

要把已知困难语言 $A$ 的困难性传给 $B$ ，方向必须是 $A\le_m^p B$ 。反向 $B\le_m^p A$ 只说明可用 $A$ 的算法解决 $B$ 。证明还必须覆盖“源是则目标是”和“目标是则源是”，且构造 $f$ 时不能调用目标判定器。

本页只定义判定语言间的一次 Karp 归约。Turing 归约允许多次、可自适应地询问目标 oracle，通常更强。

若研究的预算缩小到对数工作空间，变换本身也必须受相应约束。STCON 的 NL 完全性给出完整的对数空间归约定义、逐位输出配置图的方法，以及目标算法读取输出时的虚拟输入重算。这里的归约方向不变，但多项式时间可计算不再足以满足归约器的资源要求。

L-reduction控制优化值与误差，gap reduction保存承诺间隙，FPT 归约还约束新参数。普通 Karp 归约不会自动传递这些额外结构。例如独立集与顶点覆盖的最优值满足 $\alpha(G)+\tau(G)=n$ ，精确阈值能够取补互换；但覆盖近似解只保证 $|C|\le2\tau(G)$ 时，其补集仅有 $n-|C|\ge n-2\tau(G)$ 个点。当 $\tau(G)$ 接近 $n/2$ ，该下界可接近零，不能得到独立集的常数乘法近似。归约也不会自动保留通信量、查询次数或学习成功概率。

推论与应用

若 $A\le_m^p B$ 且 $B\in\mathbf P$ ，先算 $f(x)$ 再运行 $B$ 的判定器，得到 $A\in\mathbf P$ 。

例如已有 VC 判定器时，先把 IS 输入的阈值改成 $n-k$ ，再将同一张图交给它，其答案就是 IS 的答案；若变换时间及输出长度由 $p$ 控制、VC 算法时间由 $q$ 控制，总时间至多 $p(n)+q(p(n))$ 。这个算法方向与困难性方向一致：IS 已知困难时，IS 到 VC 的箭头才把困难性传给 VC；单独给出补集变换并没有证明 IS 已经困难。可用五边形 $C_5$ 自检：它的最大独立集为二、最小覆盖为三，所以 $k=2$ 映成覆盖阈值三，两边为是； $k=3$ 映成阈值二，两边为否。

若 $B\in\mathbf{NP}$ ，目标证书长度是 $|f(x)|$ 的多项式，而 $|f(x)|$ 又是 $|x|$ 的多项式，所以同样有 $A\in\mathbf{NP}$ 。这种“容易性沿箭头反向传播”的性质，是NP 困难性与NP 完全性的逻辑基础。

相较于可计算性中的映射归约，本页额外限制变换时间与输出长度。选用哪种归约会改变可传递的结论，因此困难性陈述必须连同归约类型书写。

分布问题的平均情形归约还要求控制前像的总概率质量。一个保持首位的正确 Karp 归约，可能把均匀输入集中到目标算法的两个稀有慢点；该页给出这份求解器性能失效的精确成本，以及概率支配条件下的完整保持证明。

参考资料

Richard M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103.
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, §§2.1–2.2.
Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, §7.4.

形式陈述 ​

独立集到顶点覆盖 ​

方向与接口边界 ​

反向链接

形式陈述

独立集到顶点覆盖

方向与接口边界