算法设计第 8 章：NP 完全性——归约、库克定理与近似算法
这一章回答一个让人不太舒服的问题：有些问题可能根本没有多项式算法，我们该怎么办。答案分两半——理论上用归约把问题分类，证明它属于 NP 完全；工程上用近似算法、随机化或剪枝给出"够用"的解。全章最有价值的不是名词，而是归约的构造手法与近似比的算法：能自己把 3-SAT 归约到团，才算真懂 NPC。
一、判定问题、P 与 NP
理论分析把优化问题转成判定问题（答案只有是/否），因为判定问题便于比较难度。"求最短回路长度"转成"是否存在长度 ≤ k 的回路"。
- P 类：存在多项式时间算法可解的判定问题。排序、最短路、二分图匹配都在 P 内。
- NP 类：给定一个候选解（证书），能在多项式时间内验证其正确性的判定问题。等价说法：存在非确定型图灵机在多项式时间内接受它。
- co-NP：补问题在 NP 中，即"能多项式验证否定答案"。
显然 P ⊆ NP，但 P 是否等于 NP 是未解难题。所有人相信 P ≠ NP，因为五十年来没人找到任何一个 NPC 问题的多项式算法。
一个常见误解：NP 不是"非多项式"（Non-Polynomial），而是"非确定型多项式"（Nondeterministic Polynomial）。NP 里全是"容易验证"的问题，不是"难解"的问题——难的是它们可能没有容易的求解方法。
二、多项式时间归约与 NP 完全性
多项式归约 L₁ ≤ₚ L₂：存在多项式时间可计算的函数 f，使 x ∈ L₁ 当且仅当 f(x) ∈ L₂。含义是"L₂ 的算法可以当 L₁ 的算法用"——L₂ 至少和 L₁ 一样难。
归约的方向极易写反：我们要证"新问题 X 是 NPC"，应当把已知的 NPC 问题归约到 X（SAT ≤ₚ X），而不是把 X 归约到 SAT。后者只能说明 X 不难，前者才说明 X 不简单。
NP 完全（NPC）：L ∈ NP，且对所有 L' ∈ NP 有 L' ≤ₚ L。 NP 难（NP-hard）：只要求所有 NP 问题可归约到它，不要求它自身在 NP 内（可以不是判定问题，如 TSP 的优化版本）。
| 概念 | 定义要点 | 是否在 NP 内 | 例 |
|---|---|---|---|
| P | 多项式时间可解 | 是 | 排序、最短路 |
| NP | 多项式时间可验证 | 是 | SAT、团、TSP 判定版 |
| NPC | NP 且 NP-hard | 是 | SAT、3-SAT、团、顶点覆盖 |
| NP-hard | 所有 NP 问题可归约到它 | 不一定 | TSP 优化版、停机问题 |
证明 X 是 NPC 的标准三步：先证 X ∈ NP（给出证书与多项式验证方法）；再选一个已知 NPC 问题 Y；构造 Y ≤ₚ X 的归约并证明等价性。
三、布尔可满足性与库克定理
SAT：给定含 n 个布尔变量的合取范式（CNF），问是否存在赋值使公式为真。 3-SAT：每个子句恰含 3 个文字。SAT ≤ₚ 3-SAT，所以 3-SAT 也是 NPC。
库克–列文定理：SAT 是 NP 完全的。证明思路是把"非确定型图灵机在多项式时间内接受 x"这一计算过程编码成布尔公式——变量描述每个时刻的纸带内容、读写头位置与状态，子句约束转移的合法性。公式长度是输入规模的多项式，可满足当且仅当机器接受。这是第一个 NPC 问题，也是所有后续归约的源头。
四、团问题的 NP 完全性证明
团问题：无向图 G 与整数 k，问是否存在 k 个顶点两两相邻。
先证团 ∈ NP：证书是 k 个顶点，验证两两相邻需 O(k²) 次检查，多项式，满足要求。
再证 3-SAT ≤ₚ 团：设公式有 k 个子句 C₁, …, Cₖ，每个子句 3 个文字。
- 为每个子句的每个文字建一个顶点，共 3k 个顶点，分成 k 组（每组对应一个子句）。
- 连边规则：两个顶点相连 当且仅当它们属于不同子句，且文字不互补（不是 x 与 ¬x）。
- 取 k = 子句数。
等价性：若公式可满足，每个子句至少有一个真文字，从每组挑一个真文字，共 k 个；它们分属不同组故两两有边，且不会互补（互补的两个文字不可能同时为真），构成 k 团。反之，若存在 k 团，因团内不能有同组顶点（同组不连边），必每组件取一个，且互不互补，给这些文字赋真即得满足赋值。归约是多项式时间的（顶点 3k 个、边 O(k²)），故团是 NPC。
同一套构造稍作修改就得到独立集（把"不互补"改成"互补"连边）与顶点覆盖（补图上的独立集），三个问题互相归约，是 NPC 家族的核心。
五、近似算法与近似比
既然精确解可能做不到，就退一步：在多项式时间内给出接近最优的解，并证明差距有界。
对最小化问题，算法 A 的近似比 ρ(n) 定义为
ρ(n) = max { C(A)/C }，其中 C 是最优值，C(A) 是算法解的值。
显然 ρ ≥ 1，越接近 1 越好。若 ρ 是常数，称常数近似比。
| 问题 | 近似比 | 方法 |
|---|---|---|
| 顶点覆盖 | 2 | 取极大匹配，两端点全选 |
| 集合覆盖 | ln n + 1 | 每步选覆盖最多未覆盖元素的集合 |
| 度量 TSP | 2（Christofides 为 1.5） | MST 双重遍历 / 匹配加欧拉回路 |
| 一般 TSP | 无常数比（除非 P = NP） | — |
| 0-1 背包 | 无常数比，但有 FPTAS | 按价值缩放后 DP |
顶点覆盖的 2-近似最值得记：反复取一条未覆盖的边 (u,v)，把 u、v 都加入解并删除所有与它们关联的边。每条选中的边至少有一个端点在最优解中，且不同选中边互不相交，故 |A| ≤ 2|C|。证明近似比的标准手法就是"找到一个下界，再说明算法解不超过下界的常数倍"*。
六、旅行商问题的近似求解
满足三角不等式的 TSP（度量 TSP）：w(u,v) ≤ w(u,x) + w(x,v)。
- 求最小生成树 T（Prim 或 Kruskal）。
- 对 T 做前序遍历得到走法，得到一个回路（允许重复访问时用"抄近路"跳过已访问点）。
近似比证明：MST 权值 ≤ 最优回路权值（删掉回路任一条边就是生成树）；双重遍历的回路权值 = 2·w(T) ≤ 2·C；由三角不等式，抄近路只会更短。故 ρ = 2。Christofides 用最小权完美匹配把奇度点配对，把比值改进到 1.5*。
没有三角不等式时，一般 TSP 不存在常数比近似——否则可以在多项式时间内判定哈密顿回路（把不存在边的权值设成极大），从而 P = NP。这是"问题的结构决定可近似性"的最好例证：多一条三角不等式，问题就从"不可近似"变成"2-近似"。
易错点
- 把 NP 理解成"非多项式"，或认为 NPC 问题"绝对没有多项式算法"（只是无人找到，且 P≠NP 未被证明）。
- 归约方向写反，把待证问题归约到 SAT。
- 证 NPC 时漏掉"该问题属于 NP"这一步。
- 近似比方向写反，最小化问题写成 C*/C。
- 对一般 TSP 声称有常数比近似，忽略了三角不等式这个前提。
这一章在整门课里的位置
本章是前七章的"天花板"：第 5、6 章的回溯与分支限界之所以重要，正因为 NPC 问题没有多项式算法，暴力加剪枝是现实答案；第 3 章的背包 DP 是伪多项式，正是它在 NPC 中的位置说明。本章的近似思想又直接连到第 10 章——用启发式与剪枝在可接受时间内逼近最优。
本文是《算法设计与分析（89 讲）》第 8 章的知识点摘要。完整板书与代码见 课程页；上一章 概率算法，下一章 子串匹配。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 算法设计与分析（89讲） 89 讲