Gap 问题与 gap reduction

形式陈述 ​

对归一化最大化问题及常数 $c>s$，gap promise problem ${\mathrm{Gap}}_{c,s}(\mathrm{\Pi })$ 要求区分

$$\text{YES: }\mathrm{OPT}(x)\ge c,\text{NO: }\mathrm{OPT}(x)\le s.$$

当 $s<\mathrm{OPT}(x)<c$ 时输入不满足 promise，算法无需给出任何保证。最小化问题的方向相反，通常写 YES 为 $\mathrm{OPT}(x)\le c$、NO 为 $\mathrm{OPT}(x)\ge s$，其中 $c<s$。

Gap-preserving reduction 是多项式时间映射 $f$，把源 promise problem 的 YES 实例映到目标 YES 区域、NO 实例映到目标 NO 区域，并显式给出阈值变换。它比只保持成员关系的普通归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。携带更多数值信息。由PCP 定理公理库PCP 定理PCP theorem每个 NP 语言都具有多项式长度、对数随机性、常数查询且带常数可靠性间隙的概率可检验证明。得到的约束系统具有 completeness $1$、soundness $s<1$：yes 实例全部约束可满足，no 实例任意证明至多满足 $s$ 比例，这正是一个常数 gap。

若最大化问题存在 $\rho$-近似算法，yes 实例输出至少 $c/\rho$，no 实例任何可行解至多为 $s$。当

$$\frac{c}{\rho }>s$$

时，比较输出值与两阈值之间的数即可解决 gap promise problem。因此 NP-hard 的 ${\mathrm{Gap}}_{c,s}$ 排除所有 $\rho <c/s$ 的多项式近似，除非 $P=NP$。最小化问题需按其比率方向公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。重新推导，不能复用同一分式。

直觉 ​

精确困难性只区分“达到最优”和“差一点”；近似算法可能绕过这条细缝。Gap 证明把 yes 与 no 的最佳目标值拉开一段常数距离，使任何跨越该距离的近似结果都泄露原问题答案。

PCP 提供局部验证的拒绝概率，gap reduction 把这段概率间隙编码进具体优化目标。两步角色不同：前者制造 gap，后者保护 gap 穿过问题变换。

例子与边界 ​

设一个约束最大化问题由 PCP 构造，yes 时所有约束可满足，no 时最多满足 $1-\epsilon$ 比例。若存在比 $1/(1-\epsilon )$ 更好的乘法近似，yes 输入的输出值会严格高于 $1-\epsilon$，而 no 输入任何解都不会超过该阈值，于是可判定原 NP 语言。

普通 SAT 到优化问题的 Karp 归约可能只保证 yes 时达到某值、no 时低一单位；当实例规模增长，这个相对 gap 趋于零，不能推出常数不可近似。必须归一化目标并证明两个阈值保持常数分离。

Promise 中间区间不是第三类必须正确分类的输入。若后续归约可能把合法源实例落入中间区间，gap 保持就失败；不能用“算法大概会选一边”补救。权重、约束数或目标缩放也必须进入阈值计算。

推论与应用 ​

Gap reduction 是从 PCP 到 Max-SAT、Label Cover、Clique 等不可近似结果的标准桥梁。每个具体结论仍需给出目标问题版本、归一化方式、completeness/soundness 阈值和近似比换算。

L-reduction 控制最优值与解误差的线性回传，gap reduction 直接保持两个 promise 区域；二者可以服务相似困难性目标，却不是同一定义。选择哪一种取决于要传递常数近似还是特定阈值间隙。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, Chs. 11 and 22.
• Vijay V. Vazirani, Approximation Algorithms, Springer, 2001, Ch. 29, PCP and hardness of approximation.