09 P/NP 理论与 NP 完全性证明

本章对应考试中的：简答 Q5（0/1 背包的多项式等价判定问题，高频）、Q6（某路径问题是否属 NP）、Q7（P、NP、NPC、NP-hard、归约、转化的定义）、NP 完全性证明 N1（TSP）/N2（SAT）（试卷6，25 分）、判断题 32～42（P/NP 高频陷阱区）、选择题第 9 题。
这一章概念多、最绕，但判断题和定义题占分大、且高度重复，把定义和几个陷阱背熟就能拿稳分。

核心考点

判定问题 是什么（判断题 41、42 直接考）。
P、NP、NP 完全（NPC）、NP 难（NP-hard） 的定义与关系（Q7、判断题 32～40）。
归约与转化 的区别（Q7、判断题 40）。
NP 完全性证明的两步法（N1、N2）。
多项式等价（Q5 背包）。

从零开始的前置知识

判定问题 vs 优化问题 vs 搜索问题

判定问题（decision problem）：答案只有"是（yes）/否（no）"的问题。例："给定图 $G$ 和整数 $k$ ， $G$ 中是否存在大小至少为 $k$ 的团？"
优化问题（optimization problem）：求最优值。例：" $G$ 中最大团的大小是多少？"
搜索/构造问题（search problem）：求一个具体的解。例："找出 $G$ 中一个最大的团。"

整套 P/NP 理论是建立在判定问题上的。

判断题 41："下列是判定问题：给定合取范式 $Γ$ ，对 $Γ$ 中所有变量求一组真值赋值使其为真"——✗ 错。"求一组赋值"是搜索/构造问题；判定问题只问"是否存在这样的赋值（yes/no）"。 判断题 42："给定图 $G$ ，求 $G$ 中最大团的尺寸 $K$ ，是判定问题"——✗ 错。"求尺寸"是优化问题；判定版本应是"是否存在尺寸 $\geq K$ 的团"。

P 类、NP 类

P 类：存在多项式时间算法就能求解的判定问题的集合。直观说就是"容易解的问题"。
NP 类：对每个"是（yes）"的实例，都存在一个多项式长度的"证书"（即一个候选解），并且能在多项式时间内验证这个证书确实证明它是 yes 实例。直观说就是"容易验证的问题"。

判断题 39："P 类是易解的问题，NP 是易被验证的问题"——✓ 对，这是标准直观刻画。

证书（certificate）：一个"声称这是 yes 实例"的证据。例如团问题，给你一组顶点（证书），你只要检查它们两两相连且数量够 $k$ ，就验证了。验证比从头求解容易得多——这是 NP 的精髓。

P 与 NP 的关系

已知 $P \subseteq N P$ （能"求解"的当然能"验证"，所以 P 一定在 NP 里）。
$P = N P$ 还是 $P ⊊ N P$ （P 是 NP 的真子集）至今没有证明，这是著名的悬而未决问题。

判断题 37："如果一个问题是 NP 问题，则它一定不是 P 问题"——✗ 错。因为 $P \subseteq N P$ ，P 问题本身就是 NP 问题。 判断题 38："如果一个问题不是 NP 问题，那么它有可能是 P 问题"——✗ 错。因为 $P \subseteq N P$ ，不是 NP 的就一定不是 P（否则它会因属于 P 而属于 NP，矛盾）。 判断题 35/36（关于能否写成 $P \subset N P$ ）：由于 $P ⊊ N P$ （真包含）尚未被证明，"断言真包含"缺乏依据。题库对这两条措辞不同的题，按其答案键：第 35 条标"⚠️ 见解析"，第 36 条"P 与 NP 不可以用 $P \subset N P$ 表示"标 ✓ 对。考试以题库答案为准，理解要点是" $P \subseteq N P$ 已知、 $P ⊊ N P$ 未证"。

NP 完全（NPC）与 NP 难（NP-hard）

NP 完全（NP-complete, NPC）：一个判定问题 $P_{1}$ 满足两条——① $P_{1} \in N P$ ；② NP 中所有其它问题都能多项式转化到 $P_{1}$ 。直观说，它是"NP 类里最难的一档"。
NP 难（NP-hard）：NP 中所有问题都能多项式归约到它（不要求它本身属于 NP），所以范围比 NPC 更广，可能比 NPC 还难。

关键关系：NPC = NP-hard $\cap$ NP。即 NP 完全问题是"既属于 NP、又是 NP 难"的问题。

判断题 32："所有问题中最难的一组是 NP 完备问题"——✗ 错。NP 完全是 NP 类内最难，不是"所有问题"中最难；NP-hard 可以更难。 判断题 33："NP 完全问题比其它所有 NP 问题都难"——✗ 错。NP 完全问题之间是等难的（互相能多项式转化），它只是"至少和其它 NP 问题一样难"，并非严格更难。 判断题 34："NP 完备问题是所有 NP 问题中最难的，目前还没找到多项式算法"——✗ 错。症结在"比其它所有都难"——NP 完全问题彼此等难；后半句"未找到多项式算法"本身是对的。

归约与转化（Q7、判断题 40）

归约（reduce）：若能用"求解 $P_{2}$ 的算法"作为子程序来求解 $P_{1}$ ，则称 $P_{1}$ 可归约为 $P_{2}$ （记 $P_{1} \leq P_{2}$ ）。直观：" $P_{2}$ 至少和 $P_{1}$ 一样难"。
转化（transform，多项式变换）：若对 $P_{1}$ 的每个实例 $I_{1}$ ，都能在多项式时间内构造出 $P_{2}$ 的一个实例 $I_{2}$ ，使得" $I_{2}$ 是 yes 实例 当且仅当 $I_{1}$ 是 yes 实例"，则称 $P_{1}$ 可多项式转化为 $P_{2}$ （记 $P_{1} \leq_{p} P_{2}$ ）。转化是归约的一种更严格的特例。

方向要记牢： $P_{1} \leq_{p} P_{2}$ 意味着" $P_{2}$ 至少和 $P_{1}$ 一样难"（因为解出 $P_{2}$ 就能解 $P_{1}$ ）。

判断题 40："若 $P_{2}$ 多项式转化为 $P_{1}$ ，则 $P_{2}$ 至少与 $P_{1}$ 一样难"——✗ 错。 $P_{2} \leq_{p} P_{1}$ 表示的是 $P_{1}$ 至少和 $P_{2}$ 一样难，方向反了。

常见的 NP（完全）问题（记几个备用）

电路可满足性（Circuit-SAT）、布尔公式可满足性（SAT）、3-CNF-SAT、团问题（Clique）、顶点覆盖（Vertex Cover）、哈密尔顿回路（Hamiltonian Cycle）、旅行商问题（TSP）、子集和问题（Subset Sum）。

答题模板

模板 F：证明问题 X 是 NP 完全的（两步）
① 证 X ∈ NP：给出一个"证书"(候选解)，说明能在多项式时间内验证它是否使 X 成为 yes 实例。
② 证 X 是 NP 难：取一个【已知的 NP 完全问题 Y】，构造多项式时间转化
   把 Y 的任意实例变成 X 的一个实例，使得 "Y 是 yes 实例 ⟺ X 是 yes 实例"。
结合①②，X 是 NP 完全的。∎

模板：证明某问题属于 NP
  给出证书 + 说明验证过程在多项式时间内完成即可。

逐题精解

Q5 0/1 背包的多项式等价判定问题（高频）

原题：写出 0/1 背包问题的一个多项式等价的判定问题，并说明为什么它们多项式等价。

前置：0/1 背包优化问题—— $n$ 件物品，物品 $i$ 重 $w_{i}$ 、值 $p_{i}$ ，背包容量 $W$ ，每件要么拿要么不拿，求能装下的最大总价值。多项式等价指两个问题能互相在多项式时间内转化求解。

判定问题：给定 $n$ 件物品（重 $w_{i}$ 、值 $p_{i}$ ）、容量 $W$ 和整数 $k$ ，问：是否存在物品子集 $S$ ，使 $\sum_{i \in S} w_{i} \leq W$ 且 $\sum_{i \in S} p_{i} \geq k$ ？

多项式等价证明（双向）：

优化 → 判定：若有解优化问题的算法，先求出最优总价值 $P^{*}$ ，则判定问题的答案就是" $P^{*} \geq k$ 是否成立"，一次调用即可。
判定 → 优化：若有解判定问题的算法，在价值范围 $0 \leq k \leq \sum_{i} p_{i}$ 上对 $k$ 做二分搜索，每次问"是否能达到价值 $k$ "， $O (\log \sum_{i} p_{i})$ 次调用就能逼出最优值 $P^{*}$ 。

两个方向都只需多项式次调用和多项式额外工作，所以二者多项式等价。

Q6 某路径问题是否属于 NP（`2011影印` 等，2 分）

原题：给定图 $G = (N, A)$ 中两点 $p, q$ 、整数 $c$ 和 $t$ 、每条边的长度 $c_{i j}$ 和遍历时间 $t_{i j}$ ，问 $G$ 中是否存在一条从 $p$ 到 $q$ 的路径，使其长度大于 $c$ 且遍历时间小于 $t$ ？该问题是否属于 NP？为什么？

答案：属于 NP。 对任意一条候选路径（证书），只需沿路径累加各边长度与时间（ $O (N)$ 时间），再检查"长度 $> c$ 且时间 $< t$ "是否成立。验证可在多项式时间内完成，故该问题属于 NP。

Q7 P/NP/NPC/NP-hard、归约、转化的定义

见上面"从零开始的前置知识"，整理成答题语言即可：

P：存在多项式时间算法求解的判定问题类。
NP：每个 yes 实例都有多项式长度证书、可在多项式时间内验证的判定问题类。
NPC： $P_{1} \in N P$ ，且 NP 中所有问题都可多项式转化到 $P_{1}$ 。
NP-hard：NP 中所有问题都可多项式归约到 $P_{1}$ （不要求 $P_{1} \in N P$ ，范围更广）。
归约：用求解 $P_{2}$ 的算法作子程序求解 $P_{1}$ ，则 $P_{1}$ 可归约为 $P_{2}$ 。
转化：对 $P_{1}$ 每个实例 $I_{1}$ 都能多项式时间构造 $P_{2}$ 实例 $I_{2}$ ，使 $I_{2}$ 为 yes 当且仅当 $I_{1}$ 为 yes。

选择题第 9 题

关于判定问题难易处理的叙述，正确的是（C）：可以由多项式时间算法求解的问题是易处理的。（多项式时间可解 = 易处理 = P 类；需要超多项式时间的才是难处理。）

NP 完全性证明题（N1、N2，`试卷6`，25 分）

N1 证明 TSP 是 NP 完全的（已知哈密尔顿回路 HAM-CYCLE 是 NPC）

原题：已知哈密尔顿回路问题 HAM-CYCLE = ${⟨ G ⟩ : G$ 是哈密尔顿图 $}$ 是 NP 完全的。证明 TSP = ${⟨ G, c, k ⟩ : G = (V, E)$ 是完全图， $c : V \times V \to Z$ ， $k \in Z$ ， $G$ 有一条耗值至多为 $k$ 的旅行商回路 $}$ 是 NP 完全的。

前置：哈密尔顿回路 是经过图中每个顶点恰好一次再回到起点的回路。完全图 是任意两个顶点之间都有边的图。

证明（两步）：

① TSP $\in$ NP：给定一个访问顶点的序列（证书），在多项式时间内沿序列累加边的耗值，并检查它是否构成一条经过所有顶点各一次的回路、且总耗值 $\leq k$ 。验证是多项式时间的，故 TSP $\in$ NP。

② HAM-CYCLE $\leq_{p}$ TSP（把哈密尔顿回路转化成 TSP）：由图 $G = (V, E)$ 构造一个完全图 $G^{'} = (V, E^{'})$ ，并定义边的耗值

c (u, v) = {\begin{cases} 0 & 若 (u, v) \in E \\ 1 & 若 (u, v) \notin E \end{cases}, 取 k = 0.

则： $G$ 有哈密尔顿回路 $⟺$ $G^{'}$ 有一条耗值 $\leq 0$ 的旅行商回路（因为耗值 $\leq 0$ 当且仅当回路只用到原图 $G$ 里真实存在的边）。这个构造在多项式时间内完成。

结合 ① ②，TSP 是 NP 完全的。 $◼$

N2 证明布尔公式可满足性 SAT 是 NP 完全的（已知电路可满足性 CIRCUIT-SAT 是 NPC）

原题：已知电路可满足性问题是 NP 完全的，证明布尔公式的可满足性 SAT 是 NP 完全的。

证明（两步）：

① SAT $\in$ NP：给定一组变量真值赋值（证书），在多项式时间内代入公式求值，即可验证公式是否为真。故 SAT $\in$ NP。

② CIRCUIT-SAT $\leq_{p}$ SAT（把电路可满足性转化成布尔公式可满足性）：对电路的每个门引入一个变量，为每个门写出刻画其输入输出关系的子句（例如 AND、OR、NOT 门各自对应的等价合取式），把所有这些子句合取起来，再附加一条"电路输出 $= 1$ "。这样得到的布尔公式可满足 $⟺$ 原电路可满足，且整个转换规模是多项式的。

结合 ① ②，SAT 是 NP 完全的。 $◼$

高频陷阱 / 易错点小结

NP 完全问题彼此等难（判断 33、34），不是"比所有 NP 都难"；NP 完全是"NP 类内最难"，不是"所有问题里最难"（判断 32）。
$P \subseteq N P$ 已知， $P = N P$ / $P ⊊ N P$ 未解决：所以"NP 就一定不是 P"（判断 37）、"非 NP 可能是 P"（判断 38）都是错的。
转化方向： $P_{2} \leq_{p} P_{1}$ 意味着 $P_{1}$ 至少和 $P_{2}$ 一样难（判断 40 反了所以错）。
判定问题只问 yes/no：求赋值（判断 41）、求最大尺寸（判断 42）都不是判定问题。
NP 完全证明永远两步：先证 $\in N P$ （给证书 + 多项式验证），再从一个已知 NPC 问题做多项式转化。
NPC = NP-hard 且 ∈ NP；NP-hard 不要求属于 NP。

自测清单

[ ] 说清判定 / 优化 / 搜索问题的区别，并判对判断 41、42。
[ ] 默写 P、NP、NPC、NP-hard 四个定义。
[ ] 说清归约与转化的区别，以及 $P_{2} \leq_{p} P_{1}$ 的"难度方向"。
[ ] 写出 0/1 背包的判定版本，并说明优化与判定双向多项式等价。
[ ] 完整写出 TSP 的 NP 完全证明两步（含 $c (u, v)$ 构造与 $k = 0$ ）。
[ ] 说出判断 32、33、34、37、38、40 各自为什么错。

09 P/NP 理论与 NP 完全性证明 ​

核心考点 ​

从零开始的前置知识 ​

判定问题 vs 优化问题 vs 搜索问题 ​

P 类、NP 类 ​

P 与 NP 的关系 ​

NP 完全（NPC）与 NP 难（NP-hard） ​

归约与转化（Q7、判断题 40） ​

常见的 NP（完全）问题（记几个备用） ​

答题模板 ​

逐题精解 ​

Q5 0/1 背包的多项式等价判定问题（高频） ​

Q6 某路径问题是否属于 NP（2011影印 等，2 分） ​

Q7 P/NP/NPC/NP-hard、归约、转化的定义 ​

选择题第 9 题 ​

NP 完全性证明题（N1、N2，试卷6，25 分） ​

N1 证明 TSP 是 NP 完全的（已知哈密尔顿回路 HAM-CYCLE 是 NPC） ​

N2 证明布尔公式可满足性 SAT 是 NP 完全的（已知电路可满足性 CIRCUIT-SAT 是 NPC） ​

高频陷阱 / 易错点小结 ​

自测清单 ​