一、为什么要学这一讲
不是为了证明定理，而是为了知道什么时候该停下来。
你会遇到这样的场景：一个需求看起来很自然（“给这些任务排一个最优顺序"“选出最划算的商品组合”），你花了三天想不出多项式算法。
⭐ 这一讲要教会你的判断是：这三天可能本来就不该花。 如果问题是 NP-难的，找多项式算法的努力等价于解决一个 50 年来最著名的开放问题。正确的做法是换一条路——近似、启发式、限制输入、或者接受指数但用得起的算法。
二、P、NP 与验证
判定问题
复杂性理论讨论判定问题（答案是 yes/no）。优化问题总能转成判定问题：
优化版：求最短的 TSP 回路
判定版：是否存在长度 ≤ k 的 TSP 回路？
⭐ 两者的难度是等价的（可以二分 k），所以只讨论判定版不损失一般性。
定义
| 类 | 定义 |
|---|---|
| P | 存在多项式时间算法求解的判定问题 |
| NP | 存在多项式时间算法验证“yes"答案的问题 |
| NP-难（NP-hard） | 所有 NP 问题都能多项式归约到它（“至少和 NP 中最难的一样难”） |
| NP-完全（NP-complete） | 既在 NP 中，又是 NP-难的 |
⚠️ NP 不是 “Non-Polynomial”，而是 “Nondeterministic Polynomial”（非确定性图灵机的多项式时间）。P ⊆ NP 是显然的（能解就能验证）。
⭐ 验证 vs 求解
NP 的本质是"给你答案，你能快速检查它对不对”：
| 问题 | 求解 | 验证（给定一个候选解） |
|---|---|---|
| 数独 | 难 | ✓ 检查每行每列每宫 |
| 因数分解 | 难（据信） | ✓ 乘起来看是不是 |
| TSP（判定版） | 难 | ✓ 加起来看是否 ≤ k |
| 哈密顿回路 | 难 | ✓ 检查是否每点恰好一次 |
| 最短路径 | 易（第 25 讲） | 易 |
P ≟ NP 问题：“能快速验证的，是否也能快速求解？”
这是 Clay 研究所的七个千禧年难题之一，悬赏 100 万美元，自 1971 年提出至今无解。绝大多数研究者相信 P ≠ NP，但没人能证明。
┌──────────────────────────────────┐
│ NP-hard │
│ ┌──────────────────┐ │
│ │ NP-complete │ 停机问题 │
│ └────────┬─────────┘ （更难） │
└───────────┼──────────────────────┘
┌───────────┼─────────┐
│ NP │ │
│ ┌────────┴──┐ │
│ │ P │ │
│ └───────────┘ │
└─────────────────────┘
（假设 P ≠ NP）
⚠️ NP-难不一定在 NP 中：停机问题是 NP-难的，但它根本不可判定，谈不上验证。
三、多项式归约
定义：问题 A 多项式归约到问题 B（记
A ≤_p B），如果存在多项式时间的变换 f，使得x 是 A 的 yes 实例 ⟺ f(x) 是 B 的 yes 实例
含义：如果能解 B，就能解 A（把 A 的实例转成 B 的实例，用 B 的算法，答案直接拿来用）。所以 B 至少和 A 一样难。
⚠️ 归约方向极易搞反
要证明"B 是 NP-难的”，必须把一个已知的 NP-难问题 A 归约到 B，即 A ≤_p B。
✓ 正确：已知难的 A ─归约到─▶ 待证的 B "B 至少和 A 一样难"
✗ 错误：待证的 B ─归约到─▶ 已知难的 A "B 不比 A 难"——什么也没证明
⭐ 记忆口诀：把「已知很难的问题」变成「你的问题」。 如果你的问题能解决那个公认很难的问题，那你的问题也很难。
归约的传递性
A ≤_p B 且 B ≤_p C ⟹ A ≤_p C
这是整个 NP-完全理论的运作方式：只要有一个起点，其他所有 NPC 问题都可以通过归约链得到。
四、Cook-Levin 定理与归约链
Cook-Levin 定理（1971）：SAT（布尔可满足性问题）是 NP-完全的。
SAT：给定一个布尔公式，是否存在变量赋值使它为真？
证明思路：任何 NP 问题都有一个多项式时间的验证器，而验证器的计算过程可以用布尔电路模拟，进而编码成一个 SAT 公式。∎
⭐ 这是第一个被证明的 NPC 问题，是整棵归约树的根。 有了它，Karp 在 1972 年一口气证明了 21 个问题是 NPC，从此这个列表膨胀到数千个。
经典归约链
SAT （Cook-Levin）
│
3-SAT
╱ │ ╲
团问题(Clique) │ 3-着色
│ 顶点覆盖 │
│ │ 图着色
独立集 ◀────────┘
│
┌─────┴─────┐
子集和 哈密顿回路
│ │
划分问题 TSP
│
0-1 背包
装箱问题
常见的 NPC / NP-难问题
| 问题 | 说明 |
|---|---|
| SAT / 3-SAT | 布尔可满足性 |
| 顶点覆盖 | 选最少顶点覆盖所有边 |
| 独立集 / 团 | 选最多互不相邻 / 互相相邻的顶点 |
| 哈密顿回路 / 路径 | 经过每个顶点恰好一次 |
| TSP | 旅行商 |
| 图着色（k ≥ 3） | 相邻顶点不同色 |
| 子集和 / 划分 | 选一个子集使和为目标值 |
| 0-1 背包（第 31 讲） | 伪多项式 DP 不算多项式 |
| 装箱 | 用最少的箱子装完物品 |
| 集合覆盖 | 选最少的集合覆盖全集 |
| 最长路径 | ⚠️ 与最短路径难度天差地别 |
| 调度问题（多机、带约束） | 大量变体 NPC |
⚠️ 注意最后两行的对比：
最短路径 ∈ P （Dijkstra，[第 25 讲]）
最长路径 NP-难 （能解它就能解哈密顿路径）
欧拉回路 ∈ P （每条边一次，判据：所有点度数为偶）
哈密顿回路 NP-完全 （每个点一次）
2-SAT ∈ P （用 SCC 求解，[第 22 讲]）
3-SAT NP-完全
⭐ 这些"一字之差、难度天差地别"的配对是本讲最值得记住的部分。 它们说明：问题的难度对表述极其敏感，不能靠直觉判断。
五、如何证明一个问题是 NPC
标准四步：
① 证明 B ∈ NP：给出一个多项式时间的验证器
② 选一个已知的 NPC 问题 A
③ 构造多项式时间的归约 f: A 的实例 → B 的实例
④ 证明等价性：x ∈ A ⟺ f(x) ∈ B （两个方向都要证）
示例：3-SAT ≤_p 独立集
给定 3-SAT 公式（m 个子句，每个 3 个文字），构造图 G：
① 每个子句造一个三角形（3 个顶点，两两相连）
② 互补的文字之间连边（x 与 ¬x）
③ 问：G 中是否存在大小为 m 的独立集？
公式：(x ∨ y ∨ ¬z) ∧ (¬x ∨ y ∨ z)
x ──── y ¬x ──── y
╲ ╱ ╲ ╱
¬z z
│ ╲___________________╱ │
└──────── ¬z—z 互补边 ────┘
x 与 ¬x 之间也有互补边
等价性证明：
- (⟹) 若公式可满足：每个子句至少有一个文字为真，从每个三角形里挑一个真文字。它们两两不相邻（不同三角形，且不可能互补——互补的两个文字不能同时为真）。得到大小 m 的独立集。✓
- (⟸) 若有大小 m 的独立集：每个三角形至多贡献 1 个顶点，共 m 个三角形，所以恰好每个三角形 1 个。互补边保证不会同时选中 x 和 ¬x，因此可以一致地赋值。每个子句都有一个真文字，公式可满足。✓ ∎
⭐ 注意这个归约的结构：三角形编码"每个子句选一个"，互补边编码"赋值必须一致"。好的归约总是把源问题的每个约束翻译成目标问题的一个结构。
六、遇到 NP-难问题怎么办
⭐ 这一节是本讲最实用的部分。 承认问题难，然后选一条路：
出路 1：近似算法
放弃最优，但给出可证明的质量保证。
近似比 ρ：算法的解与最优解之比不超过 ρ。
| 问题 | 近似算法 | 近似比 |
|---|---|---|
| 顶点覆盖 | 贪心：任取一条未覆盖的边，把两个端点都加入 | 2 |
| 度量 TSP（满足三角不等式） | 求 MST（第 24 讲)，沿它做前序遍历 | 2 |
| 度量 TSP | Christofides：MST + 奇度点的最小完美匹配 | 1.5 |
| 集合覆盖 | 贪心：每次选覆盖新元素最多的集合 | ln n |
| 装箱 | First-Fit Decreasing | 11/9 |
| 0-1 背包 | FPTAS：把价值缩放取整后 DP | 1+ε（任意精度） |
顶点覆盖的 2-近似证明：算法选出的边构成一个匹配（两两不共享顶点）。任何顶点覆盖必须至少覆盖这个匹配中的每一条边，即至少需要 |M| 个顶点。而算法用了 2|M| 个。∎
⭐ 这个证明只有两行，但它给出了一个可靠的保证——这正是近似算法相对启发式的价值。
⚠️ 有些问题连近似都难：一般 TSP（不满足三角不等式）不存在任何常数比近似（除非 P = NP）；最大团不存在 n^{1−ε} 近似。
出路 2：参数化算法
如果某个参数 k 很小，可以做到 f(k) · poly(n)——指数只在 k 上。
顶点覆盖：O(2^k · n) k = 覆盖集大小
k = 20 时完全可行，即使 n = 10⁶
⭐ 这是**固定参数可解（FPT）**理论的核心思想：把"难"隔离在一个小参数里。 实际问题中往往真的有这样的小参数（树宽、解的大小、聚类数）。
出路 3：精确的指数算法
指数不代表不能用——要看指数的底和 n 的规模。
TSP 的 Held-Karp（[第 32 讲](https://blog.ifcalm.org/posts/datastruct/32-dynamic-programming-2/)）：Θ(2ⁿn²)，n ≤ 20 可行
分支限界 + 好的剪枝：实践中常能解 n 达数千的 TSP
现代 SAT 求解器：能处理数百万变量的工业实例
ILP 求解器（Gurobi、CPLEX）：许多 NP-难问题的实用解法
⭐ 这一点非常重要，也最常被误解：“NP-完全"是关于最坏情况的论断，不是"实践中解不了"的宣判。 现代 SAT/ILP 求解器每天在工业界求解着理论上"不可解"的问题——因为真实实例往往有结构，不是最坏情况。
遇到 NP-难问题，先问：“能不能建模成 SAT 或整数规划，交给成熟的求解器？” 这往往比自己写启发式更有效。
出路 4：启发式与元启发式
无保证，但实践中常常够用：贪心、局部搜索、模拟退火、遗传算法、禁忌搜索、蚁群、大邻域搜索。
⚠️ 一定要做基线对比：很多复杂的元启发式并不比"贪心 + 局部搜索"更好，却复杂 10 倍。
出路 5：⭐ 改变问题
这是最常被忽略、却往往最有效的一条。
| 观察 | 收益 |
|---|---|
| 图是树或树宽小？ | 大量 NPC 问题在树上是线性的（第 32 讲树形 DP） |
| 图是二分图？ | 独立集、顶点覆盖变成匹配问题（第 27 讲的 König 定理） |
| 图是平面图？ | 有 PTAS，4-着色一定可行 |
| 数值范围小？ | 背包、子集和的伪多项式 DP 可用 |
| 真的需要最优吗？ | 业务上"好解"和"最优解"的差别可能只有 2%，但代价差 1000 倍 |
| 约束能放松吗？ | “最多 3 个” 改成 “最多 5 个” 可能让问题落入 P |
⭐ 最后两条尤其重要：很多"NP-难"是被过度精确的需求逼出来的。 在动手写算法之前，回去和提需求的人确认"是不是真的需要最优解”，常常能省掉全部麻烦。
七、复杂性类全景
可判定 ─────────────────────────────────────
│
├─ EXPTIME 指数时间（已知 P ⊊ EXPTIME）
│ │
│ ├─ PSPACE 多项式空间（含 NP；量化布尔公式 QBF 是完全问题）
│ │ │
│ │ ├─ NP 多项式时间可验证
│ │ │ │
│ │ │ ├─ NPC NP-完全（SAT、TSP、…）
│ │ │ ├─ NPI 中间态（因数分解、图同构——据信在此）
│ │ │ └─ P 多项式时间可解
│ │ │ ├─ NC 可高效并行
│ │ │ └─ L 对数空间
│ │ └─ co-NP
│
不可判定 ── 停机问题、Rice 定理涵盖的一切
⚠️ 图中几乎所有的包含关系是否严格都未知——P ⊆ NP ⊆ PSPACE ⊆ EXPTIME，我们只知道 P ⊊ EXPTIME。这门学科的基本问题几乎全是开放的。
八、课程收尾
回到课程首页开篇提出的三件事：
第一，把问题化归为已知结构。 现在你有了一个工具箱：散列表、堆、平衡树、图、DP。真实问题的第一步永远是识别它属于哪一类。
第二，为你的选择给出论证。 循环不变式（第 1 讲）、交换论证（第 30 讲）、势能法（第 4 讲）、归约（本讲）——这四种论证方法覆盖了本课程几乎所有的正确性证明。
第三，知道什么时候该放弃。 这一讲给出了判据和五条出路。
⭐ 最后一条也许是最重要的：本课程的每一个"最优"结论都带着前提——散列表的 O(1) 需要好的散列函数、快排的 n log n 需要随机化、Dijkstra 需要非负权、贪心需要交换论证、DP 需要无重叠依赖。把前提和结论一起记住，才是真正学会了。
随堂自测
- P 和 NP 的定义分别是什么？NP 中的 “N” 代表什么？
- 为什么讨论判定问题不损失一般性？
- 要证明 B 是 NP-难的，归约方向应该是 A ≤_p B 还是 B ≤_p A？用一句话解释为什么。
- Cook-Levin 定理说了什么？它为什么是整个理论的起点？
- 证明一个问题是 NPC 的四个步骤是什么？哪一步最容易被遗漏？
- 完成 3-SAT ≤_p 独立集 归约中"(⟸)“方向的证明。
- 最短路径在 P 中而最长路径是 NP-难的，欧拉回路在 P 中而哈密顿回路是 NPC。这说明了什么？
- 顶点覆盖的 2-近似算法是什么？完整给出它的近似比证明。
- “NP-完全"是否意味着实践中解不了？为什么现代 SAT 求解器能处理百万变量的实例？
- 遇到一个 NP-难问题，列出五条可能的出路，并说明"改变问题"为什么常常最有效。
- 举出三个"限制输入结构就让 NPC 问题变简单"的例子。