5.4 近似算法与不可近似性（PCP 定理）

5.4 近似算法与不可近似性（PCP 定理）

本节摘要：NP 难问题精确解难，近似如何？本节讲清楚近似算法、PTAS、PCP 定理、不可近似性、以及"近似到什么程度"的精细边界。读完你能理解为什么某些问题能 1.01 近似但不能 0.99 近似。

一、近似算法

NP 难问题精确解指数时间，近似算法给"接近最优"的解，多项式时间。

近似比：算法保证解质量 ≥ OPT/α（最大化）或 ≤ α·OPT（最小化），α 是近似比。α=1 是精确，α 越接近 1 越好。

PTAS（多项式时间近似方案）：对任意 ε>0，时间多项式（可能 n^f(1/ε)）给 (1±ε) 近似。f 可能是指数（如 2^(1/ε)），所以 PTAS 对小 ε 不实用。

FPTAS（完全 PTAS）：时间多项式于 n 和 1/ε，实用。如 0-1 背包有 FPTAS。

APX：有常数近似比算法的问题类。如顶点覆盖有 2 近似（APX），但一般旅行商无 PTAS（除非 P=NP）。

二、近似算法的例子

顶点覆盖：2 近似——贪心选最大匹配，取所有匹配端点。简单且最优比已知（除非 PCP 假设，无 2-ε 近似）。

旅行商（度量）：Christofides 1.5 近似——MST+最小完美匹配+欧拉回路。最优比未知（可能 4/3）。

集合覆盖：ln(n) 近似——贪心选覆盖最多未覆盖。最优比（除非 P=NP，无 c 近似 c<ln n）。

0-1 背包：FPTAS——动态规划+精度参数。

这些展示近似算法的威力——NP 难问题仍能高效给接近最优解。

三、PCP 定理

PCP 定理（Arora-Lund-Motwani-Sudan-Szegedy 1992）：NP = PCP(log, O(1))——NP 证明能写成查常数位即可验证。

直觉：传统 NP 证明要读完整证明，PCP 证明写成特殊格式，验证者随机查常数位（如 3 位）就能以高概率判断正确性。如果证明错，常数位查询以高概率发现错。

意义：

• 重新定义证明：证明可被局部检查，不需要读全。
• 不可近似性基础：PCP 蕴含许多 NP 难问题不可近似到某常数比——因为近似算法能转 PCP 验证，矛盾 NP 难。

四、不可近似性

PCP 定理让证明不可近似性成为可能：

MAX-3SAT 不可近似：PCP 转化给——MAX-3SAT（最大化满足子句数）不能近似到 7/8+ε（Håstad 1997）。即任何算法不能保证 ≥ 7/8·OPT+ε，除非 P=NP。

顶点覆盖不可近似：不能近似到 2-ε（Dinur-Safra 2002，基于 PCP 改进）。所以 2 近似是最优比（除非 P=NP）。

集合覆盖不可近似：不能近似到 (1-o(1))ln n（Feige 1998）。所以 ln n 近似接近最优。

一般旅行商不可近似：无任何常数近似（除非 P=NP），因为精确解归约。

这些结果把"近似到什么程度"和 NP 难性联系——PCP 让我们能证明"近似到某比也 NP 难"。

五、不可近似性的精细边界

不可近似性不只是"有/无"，而是精细边界：

MAX-3SAT：7/8 是阈值——能 7/8 近似（随机赋值期望 7/8），但不能 7/8+ε。所以 7/8 是"易/难"的精确边界。

顶点覆盖：2 是阈值——能 2 近似，不能 2-ε。边界明确。

集合覆盖：ln n 是阈值——能 ln n 近似，不能 (1-ε)ln n。边界含常数因子。

聚类（k-median/k-means）：常数近似可能（如 1+√3），但 PTAS 在一般度量不存在（除非 P=NP）。

这些精细边界指导算法研究——知道某比不可近似，转向其他比或问题。

六、唯一游戏猜想（UGC）

Khot 2002 提出唯一游戏猜想（Unique Games Conjecture），更强假设：

UGC：唯一游戏问题（一种特殊约束满足问题）NP 难。

UGC 蕴含更精细的不可近似性：

• 顶点覆盖不能 2-ε（UGC 下，比 PCP 强）。
• MAX-CUT 不能 0.878+ε（Goemans-Williamson 0.878 是最优，UGC 下）。
• 很多问题在 UGC 下有精确阈值。

UGC 未证，多数相信但争议大。如果 UGC 真，不可近似性边界更精细；如果假，部分边界要重审。

七、近似与硬度的意义

近似和不可近似性的价值：

1. 实际算法：NP 难问题用近似给接近最优解，是实际可行方案。

2. 理论边界：不可近似性告诉"能到什么程度"，指导算法研究。

3. PCP 深刻性：PCP 定理是复杂性理论最深刻结果之一，连接证明、近似、局部检查。

4. UGC 精细化：UGC 让不可近似性更精细，是当前焦点。

5. 与密码学联系：PCP 和不可近似性是密码学基础（如零知识证明、安全多方计算）。

八、一个近似算法的具体设计

用顶点覆盖的 2 近似展示"近似算法怎么做"。贪心策略：反复找一条两端都未被覆盖的边，把两个端点都加入覆盖集。可以证明这给出 2 近似：每次选边，最优覆盖至少包含它的一个端点（否则这条边未被覆盖），所以每选一条边，最优解至少付出 1 的代价，而我们的解为这条边付出 2——解的大小不超过最优解的 2 倍。

输入：无向图 G=(V,E)
输出：顶点覆盖 C
C ← 空集
当存在边 (u,v) 且 u、v 都不在 C 中:
    把 u、v 加入 C
返回 C
​

更精巧的版本是"最大匹配加取匹配端点"，同样 2 近似，且 Dinur-Safra 证明在 P 不等于 NP 下这是最优比（不能做到 2 减 ε）。这个例子说明近似算法设计的核心：找一个"与最优解可比"的结构（匹配），而不是盲目贪心。

九、PTAS 与 FPTAS 的工程差别

PTAS 允许时间多项式但指数依赖 1/ε（如 n 的 2 的 1/ε 次方），理论上有任意精度，实际 ε 取 0.1 就不可行；FPTAS 要求时间多项式于 1/ε，才是工程可用的"任意精度"。0-1 背包有 FPTAS（动态规划加缩放），这是教材常说的例子。反过来，很多问题（如一般的旅行商）连 PTAS 都不可能有——PCP 定理精确刻画了这种边界。所以"可近似性"本身是一个分层结构：APX 包含 PTAS 包含 FPTAS，近似算法的能力上限由此界定。

十、不可近似性与随机算法的联系

MAX-3SAT 的八分之七边界有个有趣来源：随机给每个变量赋值，每个子句被满足的概率是八分之七，期望满足八分之七的子句——所以"随机算法"直接给出八分之七近似。Håstad 定理说八分之七加 ε 不可能（除非 P 等于 NP）。这个巧合不是偶然：随机赋值提供了"免费的下界"，而 PCP 保证没有更好的确定性算法。近似算法、随机算法、不可近似性三者在这里交汇，是整章最值得回味的点。

⚠️ 常见误读：以为"近似算法总是可能"。PCP 定理证明很多 NP 难问题不可近似到某比——如顶点覆盖不能 2-ε，集合覆盖不能 (1-ε)ln n。近似有理论边界。

💡 关键直觉：近似算法给 NP 难问题接近最优解（顶点覆盖 2、TSP 1.5、集合覆盖 ln n、背包 FPTAS）。PCP 定理（NP=PCP(log,O(1))）是证明可局部检查，蕴含不可近似性（MAX-3SAT 7/8、顶点覆盖 2、集合覆盖 ln n）。UGC（Khot）让边界更精细（MAX-CUT 0.878）。指导算法研究，连接密码学。

本章回顾

• 近似算法：NP 难问题多项式时间给接近最优，近似比 α，PTAS/FPTAS/APX。
• 例子：顶点覆盖 2、TSP 度量 1.5、集合覆盖 ln n、背包 FPTAS。
• PCP 定理：NP=PCP(log,O(1))，证明可查常数位验证，重新定义证明。
• 不可近似性：PCP 蕴含——MAX-3SAT 7/8+ε、顶点覆盖 2-ε、集合覆盖 (1-ε)ln n、一般 TSP 无常数。
• 精细边界：7/8、2、ln n 是易/难精确阈值，指导算法研究。
• UGC：唯一游戏猜想，更强假设，蕴含更精细边界（MAX-CUT 0.878）。
• 意义：实际算法、理论边界、PCP 深刻性、UGC 精细化、密码学联系。