第 34 章 NP 完全性 (NP-Completeness)
核心结论
-
复杂度类 P 与 NP：P 是「多项式时间可判定」的决策问题类；NP 是「多项式时间可验证（certified）」的决策问题类；显然 P ⊆ NP，是否相等是 1971 年至今未决的开放问题。
-
NP 完全 (NP-Complete)：若问题 \(L \in\) NPC，则 (1) \(L \in\) NP 且 (2) 每个 \(L' \in\) NP 可多项式归约到 \(L\)（记 \(L' \leq_P L\)）；NPC 是 NP 中「最难」的问题类。
-
多项式时间归约 (Polynomial-Time Reduction)：若存在多项式时间可计算的函数 \(f\) 使 \(x \in L_1 \Leftrightarrow f(x) \in L_2\)，则 \(L_1 \leq_P L_2\)；归约是「一个问题的难度不超过另一个」的形式化。
-
判定问题与优化问题：NP 完全性仅适用于「是/否」判定问题；优化问题可转化为等价的判定问题（参数化阈值），故优化问题的难解性可由判定问题的 NP 完全性推导。
-
证明 NP 完全性的方法：先证 \(L \in\) NP（多项式时间可验证 certificate），再从已知 NP 完全问题（如 CIRCUIT-SAT、3-CNF-SAT）通过多项式归约证明。若任一 NPC 问题可解，则 P = NP（Theorem 34.4）。
-
常见 NPC 问题：CIRCUIT-SAT、3-CNF-SAT、团问题（CLIQUE）、子集和、Hamilton 圈、独立集、顶点覆盖、TSP（决策版）、图着色等——这些问题的多项式算法都不存在。
|
本章主旨
本章是算法理论的核心：从可解性角度把问题分为「多项式可解」（P）、「多项式可验证」（NP）、「NP 最难」（NP-Complete）。意义在于：（1）如果能证明一个问题 NP 完全，则应放弃寻找精确多项式算法，转向近似算法（第 35 章）、特殊情形、或启发式；（2）NPC 问题之间相互归约构成一张「等价网络」，从 CIRCUIT-SAT 开始逐步扩展到 SAT、Hamilton 圈、TSP 等。P vs NP 问题是数学/计算机科学最重要的开放问题——若 P = NP 则所有 NPC 问题都有多项式算法（密码学破灭）；若 P ≠ NP 则当今主流猜想成立。 |
一、核心概念
本章围绕 6 个核心概念展开：从问题形式化、P/NP 复杂度类、多项式归约，到 NP 完全性定义、第一个 NPC 问题、归约方法论。
| 概念 | 定义 + 重要性 | 实现提示 |
|---|---|---|
决策问题与语言 |
决策问题 = 输入集合 \(I\) 到 \(\{0, 1\}\) 的函数；对应语言 \(L = \{x \in \{0,1\}^* : Q(x) = 1\}\)。 |
§34.1；NP 完全性只针对决策问题；优化问题通过阈值参数化转为决策问题。 |
复杂度类 P |
多项式时间 可判定 的语言类；等于可被多项式时间算法 接受 的语言（Theorem 34.2）。 |
§34.1；定义 \(P = \{L : \exists A, \forall x, A(x) \text{ decides } L \text{ in } O(\lvert x \rvert^k)\}\)。 |
复杂度类 NP |
多项式时间 可验证 的语言类；存在证书 \(y\)（\(\lvert y \rvert = O(\lvert x \rvert^c)\)）使 verifier 在多项式时间判定。 |
§34.2；定义 \(L = \{x : \exists y, A(x, y) = 1\}\)，A 多项式时间；P ⊆ NP。 |
多项式时间归约 |
函数 \(f: \{0,1\}^* \to \{0,1\}^*\) 多项式时间可计算且 \(x \in L_1 \Leftrightarrow f(x) \in L_2\)；记 \(L_1 \leq_P L_2\)。 |
§34.3；Lemma 34.3：若 \(L_1 \leq_P L_2\) 且 \(L_2 \in P\)，则 \(L_1 \in P\)。 |
NP 完全性 (NPC) |
语言 \(L\) 是 NP 完全若 (1) \(L \in\) NP 且 (2) \(\forall L' \in NP, L' \leq_P L\)。 |
§34.3；Theorem 34.4：若任一 NPC 问题 ∈ P 则 P = NP。 |
CIRCUIT-SAT 与 SAT 归约 |
CIRCUIT-SAT 是「给定布尔电路是否存在满足输入使其输出 1」（第一个被证明的 NPC）；3-CNF-SAT、CLIQUE、Hamilton 圈都可归约到。 |
§34.3-34.5；CIRCUIT-SAT 是 NPC 证明的起点；后续归约构成「NPC 网络」。 |
二、详细笔记
2.1 抽象问题与编码
What：抽象决策问题 \(Q\) 是集合 \(I\)（实例）到 \(\{0, 1\}\)（解）的二元关系；具体问题 = 抽象问题 + 编码 \(e: I \to \{0,1\}^*\)。
Why：要让计算机求解问题，必须先把抽象对象（整数、图、公式）编码为比特串；但编码的「合理程度」应不影响多项式可解性——这就是 Lemma 34.1：多项式相关的两种编码下，多项式可解性相同。
How：
| 概念 | 形式化 |
|---|---|
抽象决策问题 |
函数 \(Q: I \to \{0, 1\}\) |
编码 |
函数 \(e: I \to \{0, 1\}^*\) |
具体问题 |
\(e(Q)(x) = Q(i)\) 其中 \(x = e(i)\) |
多项式相关 |
若存在多项式时间 \(f_{12}, f_{21}\) 互相转换 \(e_1 \leftrightarrow e_2\) |
标准编码 |
用 ASCII 表示对象；假设所有编码多项式相关（二进制/三进制表示等） |
引理（Lemma 34.1）：若编码 \(e_1, e_2\) 多项式相关，则 \(e_1(Q) \in P \Leftrightarrow e_2(Q) \in P\)。
When：分析「问题本身的难度」而非「编码方式带来的伪难度」；如用一进制表示整数会让算法显得多项式（实际指数），这正是要排除的。
Example：SHORTEST-PATH（优化）：实例 = (G, u, v)，解 = 最短路径长度；PATH（决策）：实例 = (G, u, v, k)，解 = 1 iff 存在长度 ≤ k 的路径。优化问题的难度不小于其对应决策问题。
2.2 复杂度类 P 与形式语言
What：P = 「多项式时间可判定」的语言类；接受（accept）vs 判定（decide）：接受只对属于语言的串输出 1，对不属于的可无限循环；判定必须对所有输入明确输出 0/1。
Why：接受/判定的区分对 NP 类定义至关重要——NP 类基于「接受+证书」，而 P 类基于「判定」（Theorem 34.2 证明二者等价：可被多项式接受的也能被多项式判定）。
How：
| 语言类 | 定义 |
|---|---|
接受 |
\(L \in \text{accepted by } A\) iff \(\forall x \in L, A(x) = 1\)（但 \(x \notin L\) 时 A 可能不停） |
判定 |
\(L \in \text{decided by } A\) iff \(\forall x, A(x) = 1 \Leftrightarrow x \in L\) |
P（接受版） |
\(P = \{L : L \text{ 被某多项式时间算法接受}\}\) |
P（判定版） |
\(P = \{L : L \text{ 被某多项式时间算法判定}\}\) |
定理 |
这两个定义等价（Theorem 34.2） |
形式语言视角：每个决策问题 \(Q\) 对应语言 \(L = \{x : Q(x) = 1\}\)；语言类的成员判定即算法对 \(x\) 的输出。
When：定义复杂度类、证明上下界、设计算法时；Theorem 34.2 的构造性证明（模拟 cn^k 步后超时则拒绝）展示「接受→判定」的转换。
Example：PATH ∈ P：BFS 计算最短路径长度，与 k 比较，BFS 时间 \(O(V+E)\) ⊆ 多项式。
2.3 复杂度类 NP 与可验证性
What：NP 是「多项式时间可验证」的语言类——存在双输入算法 \(A(x, y)\)，\(y\) 为证书，\(A\) 多项式时间且 \(L = \{x : \exists y, A(x, y) = 1\}\)。
Why：很多问题（如 Hamilton 圈、子集和）我们不知道是否可多项式求解，但若给定一个「声称的解」（证书）则可多项式验证——这定义了 NP 类；它是 P 类的「自然上界」。
How：
| 关键点 | 形式化 |
|---|---|
证书 |
串 \(y\)，长度 \(\lvert y \rvert = O(\lvert x \rvert^c)\) |
验证算法 |
双输入 \(A(x, y)\)，多项式时间 |
NP 定义 |
\(L \in NP \Leftrightarrow \exists A, c: L = \{x : \exists y, A(x, y) = 1, \lvert y \rvert = O(\lvert x \rvert^c)\}\) |
直观 |
「有解存在证书；无解则任何证书都不通过」 |
关系 |
\(P \subseteq NP\)（P 中算法忽略证书仍能判定） |
开放问题 |
P = NP? |
When：理解「可验证 vs 可求解」的区别；这是 P vs NP 问题的核心。
Example：HAM-CYCLE ∈ NP：证书 = 顶点的哈密尔顿排列，验证算法检查每条相邻边都在 E 中，时间 \(O(\lvert V \rvert^2)\)；类似地 3-CNF-SAT 证书 = 变量赋值。
2.4 多项式时间归约
What：语言 \(L_1 \leq_P L_2\) 若存在多项式时间可计算的归约函数 \(f\) 满足 \(x \in L_1 \Leftrightarrow f(x) \in L_2\)。
Why：归约是「问题相对难度」的形式化——若 \(L_1 \leq_P L_2\) 且 \(L_2\) 多项式可解，则 \(L_1\) 也多项式可解（Lemma 34.3）；反之若 \(L_1\) 已知不可多项式求解，则 \(L_2\) 也不可。
How：
| 应用 | 推论 |
|---|---|
证明下界 |
若 \(L_1\) 已知 NP-hard，\(L_1 \leq_P L_2\) ⇒ \(L_2\) 也 NP-hard |
证明上界 |
若 \(L_2 \in P\)，\(L_1 \leq_P L_2\) ⇒ \(L_1 \in P\)（Lemma 34.3） |
归约方向 |
「易」归约到「难」说明二者同等难；「难」归约到「易」是矛盾的 |
传递性 |
\(L_1 \leq_P L_2\) 且 \(L_2 \leq_P L_3\) ⇒ \(L_1 \leq_P L_3\) |
When：证明新问题是 NP 完全；证明问题 A 不比 B 难；构造算法（用 B 的算法解 A）。
Example：Hamilton 圈 ≤_P TSP：给定图 G 构造完全图 G'，G 中边 cost = 1，其他 cost = 2；G 有 Hamilton 圈 ⇔ G' 有 cost = n 的 TSP 回路。
2.5 NP 完全性与 CIRCUIT-SAT
What：语言 \(L\) 是 NP 完全 (NPC) 若 (1) \(L \in\) NP 且 (2) 对每个 \(L' \in\) NP，\(L' \leq_P L\)；CIRCUIT-SAT 是「给定布尔电路，是否存在输入使其输出 1」——Theorem 34.5/34.6 证明它是第一个 NPC。
Why：NPC 问题的核心性质——若其一 ∈ P 则 P = NP（Theorem 34.4）；一旦有「第一个 NPC」（CIRCUIT-SAT），后续 NPC 证明只需从它归约。
How：
| 概念 | 形式化 |
|---|---|
NP-hard |
仅满足性质 (2)，未必 ∈ NP |
NPC |
NP-hard 且 ∈ NP |
Theorem 34.4 |
若任一 NPC ∈ P 则 P = NP |
CIRCUIT-SAT |
第一个 NPC（Cook-Levin 定理）：CIRCUIT-SAT ∈ NP（证书 = 输入赋值），∀L' ∈ NP, L' ≤_P CIRCUIT-SAT |
后续归约 |
CIRCUIT-SAT → SAT → 3-CNF-SAT → 大量 NPC（图论、调度、网络） |
证明 CIRCUIT-SAT 是 NPC 的核心思路：任取 \(L' \in NP\)，设其验证算法 A；对每个输入 \(x\)，构造模拟 A 在 \((x, y)\) 上运行的电路——A 输出 1 当且仅当存在 y 使电路输出 1。
When：面对新问题时，第一步先查 NPC 列表（Garey & Johnson）；若 NPC，转向近似/启发式（35 章）；若未列入，尝试从已知 NPC 归约。
Example：归约链：CIRCUIT-SAT → SAT → 3-CNF-SAT → CLIQUE / VERTEX-COVER / HAM-CYCLE / SUBSET-SUM / TSP。
2.6 NP 完全性证明方法论
What：证明问题 \(L\) 是 NPC 的标准三步：(1) 证明 \(L \in\) NP；(2) 选择已知 NPC 问题 \(L'\)；(3) 构造 \(L' \leq_P L\) 的多项式时间归约。
Why：方法论标准化降低 NPC 证明难度；选合适的「已知 NPC」是关键——通常选问题结构与 L 相似的。
How：
| 步骤 | 内容 |
|---|---|
常见陷阱 |
1. L ∈ NP |
给出证书 + 多项式时间验证算法 |
证书长度需多项式有界；验证时间需多项式 |
2. 选 L' |
从已知 NPC 中选与 L 结构相似的 |
不要从 P 中选 |
3. 构造 f |
设计多项式时间归约函数 \(f(x) = x'\) |
关键：\(x \in L' \Leftrightarrow f(x) \in L\) |
4. 证明等价 |
双向证明：若 \(x \in L'\) 则 \(f(x) \in L\)，反之亦然 |
等价性是核心，不能只证单向 |
5. 多项式时间 |
归约函数 \(f\) 本身必须多项式时间可计算 |
常被忽略——构造本身可能指数时间 |
典型归约技巧：组件设计（gadget）、子句编码为图顶点、变量编码为边/节点选择、阈值参数化等。
When：面对新优化/决策问题时；证明其 NP 完全性以否定精确多项式算法的存在性。
Example：VERTEX-COVER ≤_P CLIQUE：G 的顶点覆盖 V' 与补图 \bar{G} 的独立集一一对应；独立集与 clique 在补图下互换 → VERTEX-COVER 是 NPC。
三、关键图表
|
核心公式对照表
|
四、思维导图
mindmap
root((第 34 章 NP完全性))
问题与编码
抽象决策问题
标准编码
多项式相关
P与NP
P多项式判定
NP多项式验证
P包含于NP
多项式归约
归约函数f
难易传递
Lemma 34.3
NP完全
定义两条
CIRCUIT-SAT起点
Theorem 34.4
归约链
3-CNF-SAT
HAM-CYCLE
CLIQUE
VERTEX-COVER
SUBSET-SUM
证明方法
选已知NPC
设计f
双向等价
多项式时间五、重点与易错点
-
P vs NP 是开放问题——不要在任何证明中假定 P = NP 或 P ≠ NP，除非是反证法明确假设。
-
NP 完全性 只针对决策问题；优化问题 NP 完全性需先转化为决策问题（如 PATH = SHORTEST-PATH + 阈值 k）。
-
证明 \(L \in\) NP 必须明确给出证书 \(y\) 和多项式验证算法；忘记证书或验证时间指数都是常见错误。
-
多项式时间归约的方向：「难」→「易」是有效证明下界；「易」→「难」只能说明后者也不比前者难（等价于归约传递性）。
-
归约函数 \(f\) 本身必须多项式时间可计算——很多人忘记这一步，例如对 NP 完全的优化问题直接枚举构造 \(f\) 是指数时间。
-
「等价性」是双向的：\(x \in L' \Leftrightarrow f(x) \in L\) 必须双向证明——只证单向会破坏归约的有效性。
-
CIRCUIT-SAT 是 第一个 NPC（Cook-Levin 定理），证明较复杂——后续 NPC 证明通常从 3-CNF-SAT 开始归约即可。
-
区分 NP (verifiable)、NP-hard (as hard as NP)、NPC (NP + NP-hard)；co-NP 与 NP 的关系是另一个未解问题。
-
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME；只有 P ⊆ NP 是已证的；后续包含关系可能严格也可能相等。
-
工程意义：若证明某问题 NPC，应转而寻找 (a) 指数算法在小数据上可接受、(b) 重要特殊情形的多项式算法、(c) 近似算法（35 章）或启发式。
-
「多项式相关」的编码要求排除一进制编码等「退化」表示；否则所有多项式时间问题都可被「伪多项式」算法「假装」解决。
-
Theorem 34.2 的接受/判定等价证明是非构造性的——只知道界存在，不知道具体界；与 P 问题构造性的多项式算法不同。
-
SAT（任意子句长）可多项式归约到 3-CNF-SAT（子句长恰好 3）——这是归约方法学的经典案例。