NP 完全(1)：P, NP 与 NP 完全

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为NP完全问题（基础），包括P与NP、Karp 归约、NP-hard与NP完全等。

P 与 NP

P 类 (Polynomial Time)

• 定义：存在多项式时间图灵机可解决的决策问题集合

• 示例：路径问题、最大流问题、素数判定

NP 类 (Nondeterministic Polynomial Time)

• 定义：存在多项式时间验证机的决策问题集合

• 示例：SAT 问题、顶点覆盖问题、哈密顿路径问题

P 与 NP 关系

• $\bm{\mathrm{P} \subseteq \mathrm{NP}}$：所有 P 类问题都是 NP 类问题
• 未知问题：是否$\mathrm{P} = \mathrm{NP}$？

归约与 NP 完全性

卡普归约 (Karp Reduction)

• 定义：决策问题 $f$ 能归约到决策问题 $g$，是指存在一个图灵机 $\mathcal{A}$ 能在多项式时间内将一个 $f$ 实例转换为正确性相同的 $g$ 实例，记作 $f \le_k g$
• 理解：这表明 $g$ 的难度略高于 $f$
• 传递性：如果 $f \le_k g$，$g \le_k h$，那么 $f \le_k h$

经典归约示例

SAT 归约到 3SAT

• 方法：引入新变量，将长字句拆分为最多三个文字的短字句
• 例子：

$$\phi = (x_1 \lor x_2 \lor \lnot x_3 \lor \lnot x_4 \lor x_5 \lor x_6)$$

$$\phi' = (x_1 \lor x_2 \lor y_1) \land (\lnot y_1 \lor \lnot x_3 \lor y_2) \land (\lnot y_2 \lor \lnot x_4 \lor y_3) \land (\lnot y_3 \lor x_5 \lor x_6)$$

• 解释：$\phi$ 是一个正确的 SAT 实例当且仅当 $\phi'$ 是一个正确的 3SAT 实例

3SAT 归约到独立集

• 方法：
  1. 对每个字句，构造三角形，其中每个顶点代表一个文字
  2. 连接代表互为否定文字的顶点
  3. 设独立集问题 $k$ 为字句数
• 解释：要证明构造的实例和原实例的正确性相同

独立集归约到顶点覆盖

• 方法：$S$ 是 $G$ 的独立集 $\iff$ $V - S$ 是 $G$ 的顶点覆盖

独立集归约到团问题（Clique）

• 方法：$S$ 是 $G$ 的独立集 $\iff$ $S$ 是 $\bar{G}$ 中的团

NP-hard 与 NP 完全

• NP-hard：如果对任意 $g \in \mathrm{NP}:g \le_k f$，那么 $f$ 是 NP-hard 问题
• NP-complete：如果 $f \in \mathrm{NP}$ 并且对任意 $g \in \mathrm{NP}: g \le_k f$，那么 $f$ 是 NP-complete 问题
• Cook-Levin 定理：SAT 是 NP-complete 问题
• NP-complete 证明步骤：
  1. 证明问题属于 NP 类
  2. 选择已知 NP 完全问题 $f$
  3. 构造从 $f$ 到目标问题的多项式时间归约

注：本文中所有图片均来自张宇昊老师的课程PPT。