NP 完全理论

问题类型

易解问题和难解问题

通常将存在多项式时间算法的问题看作是易解问题（Easy Problem）。例如排序问题、查找问题等。

而将需要指数时间算法解决的问题看作是难解问题（Hard Problem）。例如旅行商问题、图着色问题等。

图灵停机问题则属于不可解问题。

P 类问题和 NP 类问题

• P 类问题可以用多项式时间的确定性算法来进行判定或求解。具体来说，P 问题是指多项式时间内可解的问题
• NP 类问题可用多项式时间的非确定性算法来进行判定或求解。具体来说，NP 问题是指多项式时间内可以验证一个解的问题。所有 NP 问题都是判定问题。

注：

1. 多项式时间：$O(n)$、$O(\log n)$、$O(n^c)$；非多项式时间：$O(2^n)$、$O(n!)$。
2. $\textnormal{P} \subseteq \textnormal{NP}$
3. 判定问题：仅仅要求回答 True 或 False 的问题。判定问题的特点是证明比求解容易。

NP 问题

最优化问题可以与一个判断问题对应：

• 最优化问题：$x$ 取何值时，$f(x)$ 取最小（大）值？
• 判定问题：给定 $f(x)$，问是否存在常数 $k$ 使得 $f(x)$ 取最小（大）值？

如何对应？

• 若判定问题多项式时间可解，则采用二分搜索策略即可。
• 反之，若已求解最优化问题，就已求解判定问题。

NP 完全问题

定义：问题 $A$ 是一个 NP 完全问题，则有

1. $A \in \textnormal{NP}$（多项式时间可验证解是否正确）
2. 且对 $\forall B \in \textnormal{NP}, B \leqslant_p A$（任意 NP 问题 $B$ 都可在多项式时间归约到 $A$）

注：

1. NP 问题包含 P 问题和 NP 完全问题。
2. P 问题和 NP 问题是否存在交集尚未定论，但目前学界普遍认为二者不存在交集。

NP 完全性的意义

• 若某个 NP 完全问题多项式时间可解，则所有 NP 问题均可多项式时间求解，从而有 $\textnormal{P} = \textnormal{NP}$。
• 若能证明某个 NP 问题不存在多项式时间求解算法（即 $\textnormal{P} \ne \textnormal{NP}$），则所有 NP 完全问题都不存在多项式时间求解算法，从而有 $\textnormal{NP-C} \cap P = \emptyset$。

因此，NP 完全问题是 NP 问题中最难的。

我们可以用下面的 Venn 图来表示这些概念之间的关系：

NP 完全性的证明

证明问题 $A$ 是 NP 完全问题分两步：

1. $A$ 是一个 NP 问题（多项式时间可验证解是否正确）。
2. 从一个已知的 NP 完全问题 $A'$，多项式时间归约到 $A$ 的一个实例 $A''$，证明 $A'$ 有解当且仅当 $A''$ 有解。