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. 判定问题:仅仅要求回答 TrueFalse 的问题。判定问题的特点是证明比求解容易。

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 完全问题

  • 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 完全问题分两步:

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