问题类型
易解问题和难解问题
通常将存在多项式时间算法的问题看作是易解问题（Easy Problem）。例如排序问题、查找问题等。
而将需要指数时间算法解决的问题看作是难解问题（Hard Problem）。例如旅行商问题、图着色问题等。
图灵停机问题则属于不可解问题。
P 类问题和 NP 类问题
- P 类问题可以用多项式时间的确定性算法来进行判定或求解。具体来说，P 问题是指多项式时间内可解的问题
- NP 类问题可用多项式时间的非确定性算法来进行判定或求解。具体来说，NP 问题是指多项式时间内可以验证一个解的问题。所有 NP 问题都是判定问题。
注：
- 多项式时间：$O(n)$、$O(\log n)$、$O(n^c)$；非多项式时间：$O(2^n)$、$O(n!)$。
- $\textnormal{P} \subseteq \textnormal{NP}$
- 判定问题：仅仅要求回答
True或False的问题。判定问题的特点是证明比求解容易。
NP 问题
最优化问题可以与一个判断问题对应：
- 最优化问题：$x$ 取何值时，$f(x)$ 取最小（大）值？
- 判定问题：给定 $f(x)$，问是否存在常数 $k$ 使得 $f(x)$ 取最小（大）值？
如何对应？
- 若判定问题多项式时间可解，则采用二分搜索策略即可。
- 反之，若已求解最优化问题，就已求解判定问题。
NP 完全问题
定义：问题 $A$ 是一个 NP 完全问题，则有
- $A \in \textnormal{NP}$（多项式时间可验证解是否正确）
- 且对 $\forall B \in \textnormal{NP}, B \leqslant_p A$（任意 NP 问题 $B$ 都可在多项式时间归约到 $A$）
注：
- NP 问题包含 P 问题和 NP 完全问题。
- P 问题和 NP 问题是否存在交集尚未定论，但目前学界普遍认为二者不存在交集。
一些基本的 NP 完全问题
- SAT 问题（布尔可满足性问题）
- 最大团问题
- 图着色问题
- 哈密尔顿回路问题
- TSP 问题（旅行商问题）
- 顶点覆盖问题
- 最长路径问题
- 子集和问题
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 完全问题分两步：
- $A$ 是一个 NP 问题（多项式时间可验证解是否正确）。
- 从一个已知的 NP 完全问题 $A’$，多项式时间归约到 $A$ 的一个实例 $A’’$，证明 $A’$ 有解当且仅当 $A’’$ 有解。