第 10 章难解问题

P、NP、多项式归约与 NP 完全性

Source scope
主要依据教材第 10 章：中文印刷页 289–326，对应 PDF p.302–339/341。目录主线为 P/NP、SAT 的 NP 完全性、约束可满足性与 3SAT，以及独立集、顶点覆盖、哈密顿回路和 TSP 等 NP 完全问题。

1 0. 从“能算”到“能高效算”

第 9 章区分可判定与不可判定。第 10 章进一步问：

即使问题可判定，是否能在可接受时间内求解？

复杂度理论通常把多项式时间看作“可行计算”的第一近似。

2 1. P 类

若一个判定问题可由确定型图灵机在输入长度 \(n\) 的某个多项式时间

\[ O(n^k) \]

内解决，则属于 \(P\)。

重要的是渐近增长阶，而不是具体机器常数。

2.1 1.1 模型稳健性

合理的确定型计算模型之间通常只产生多项式级模拟开销，因此“是否属于 P”对模型细节较稳健。

3 2. NP 类

一个语言属于 \(NP\)，若满足等价表述之一：

可由非确定型 TM 在多项式时间内接受；
对每个 yes-instance，存在多项式长度证书 \(c\)，且确定型验证器能在多项式时间验证。

第二种“证书 + 验证器”视角更实用。

例如 Hamiltonian cycle 的证书可以是一条顶点排列；验证是否构成合法回路只需多项式时间。

显然：

\[ P\subseteq NP. \]

是否 \(P=NP\) 是核心未解问题。

4 3. 多项式时间归约

定义

\[ A\le_p B \]

若存在多项式时间可计算函数 \(f\)，满足

\[ x\in A\iff f(x)\in B. \]

这意味着 \(B\) 至少和 \(A\) 一样难（在多项式归约意义下）。

若

\[ A\le_p B, \quad B\in P, \]

则 \(A\in P\)。

5 4. NP-hard 与 NP-complete

语言 \(B\) 是 NP-hard，如果对所有 \(A\in NP\)，都有

\[ A\le_p B. \]

若再满足

\[ B\in NP, \]

则 \(B\) 是 NP-complete。

证明一个新问题 \(B\) NP 完全，标准模板：

证明 \(B\in NP\)；
选已知 NP 完全问题 \(A\)；
构造 \(A\le_p B\)；
证明构造正确且规模多项式。

6 5. SAT

布尔可满足性问题 SAT：给定布尔公式 \(\phi\)，问是否存在变量赋值使 \(\phi\) 为真。

SAT 属于 NP：证书就是变量赋值，代入验证即可。

Cook–Levin 定理证明：

\[ \boxed{SAT\text{ 是 NP-complete}}. \]

6.1 5.1 Cook–Levin 证明思想

对任意多项式时间 NTM \(M\) 和输入 \(w\)，把一个接受计算编码成多项式规模的布尔公式。

变量描述“时间 \(t\)、带位置 \(i\) 上是什么符号/状态”等局部事实；约束保证：

初始配置正确；
每个单元取唯一内容；
相邻时间步符合 TM 转移规则；
最终出现接受状态。

因此公式可满足，当且仅当 \(M\) 有一条接受计算路径。

7 6. CNF、CSAT 与 3SAT

CNF 是“合取的析取”：

\[ C_1\land C_2\land\cdots\land C_m, \]

每个 \(C_i\) 是若干文字的析取。

3SAT 要求每个子句最多/恰含三个文字（具体形式按教材约定）。

通过引入辅助变量，可把一般 CNF 子句拆成 3-CNF，同时保持可满足性。

这一步是很多图问题归约的常用起点。

8 7. 独立集与顶点覆盖

8.1 7.1 独立集

图 \(G=(V,E)\) 中，顶点集 \(S\) 若任意两点之间都没有边，则为独立集。

判定问题：是否存在大小至少 \(k\) 的独立集？

8.2 7.2 顶点覆盖

\(C\subseteq V\) 若每条边至少有一个端点在 \(C\) 中，则为顶点覆盖。

关键互补关系：

\[ S\text{ 是独立集} \iff V-S\text{ 是顶点覆盖}. \]

因此很多归约可以非常直接地在二者之间转换参数：

\[ |C|=|V|-|S|. \]

9 8. 哈密顿回路

Hamiltonian cycle 要求一个简单回路恰好访问每个顶点一次。

与 Euler 回路不同：

Euler：每条边一次；
Hamiltonian：每个顶点一次。

后者是典型 NP 完全问题。

归约构造中常用“图 gadget”强迫路径表示变量选择或逻辑约束。

10 9. TSP

旅行商判定版：给定带权完全图和界 \(B\)，是否存在访问每个顶点一次并回到起点、总成本不超过 \(B\) 的巡回？

从 Hamiltonian cycle 可归约到 TSP：

原图中的边赋低成本；
非边赋高成本；
选择阈值使低成本巡回存在当且仅当原图有 Hamiltonian cycle。

11 10. 归约中最重要的“两个方向”

构造 \(f(x)\) 后，必须证明：

11.0.1 完备性

若原实例 yes，则新实例 yes。

11.0.2 健全性

若新实例 yes，则原实例 yes。

很多错误归约只证明了其中一个方向。

12 11. P vs NP 的含义

若任何一个 NP 完全问题属于 P，则

\[ P=NP. \]

反之，如果能证明某个 NP 完全问题不属于 P，则

\[ P\ne NP. \]

因此 NP 完全问题把大量不同领域的组合问题“绑定”在同一个复杂度命运上。

13 12. 常见错误

证明 NP 完全时只证明 NP-hard，忘记 \(B\in NP\)；
归约方向反了；
把优化版和判定版混用而不说明；
构造规模指数膨胀，仍声称是多项式归约；
混淆 Hamiltonian 与 Euler；
认为 \(NP\) 表示“non-polynomial”；正确是 nondeterministic polynomial time。

14 13. 本章知识地图

P ⊆ NP
     |
     +-- SAT is NP-complete
             |
             +--> 3SAT
             +--> Independent Set
             +--> Vertex Cover
             +--> Hamiltonian Cycle
             +--> TSP

Known NP-complete A --poly reduction--> target B