NP 完全性¶

计算模型¶

Deterministic Turing Machine：处于某个状态，读取到某个字符的时候，函数告诉我们下一个状态、应该写下的字符；
Non-Deterministic Turing Machine：函数的值域是之前的幂集，也就是说，可以选择很多路径。

复杂类¶

时间复杂度¶

我们考虑一族函数 $f(n)$。称一个问题是：

DTIME($f(n)$) 的，如果求解规模为 $n$ 的问题的确定性图灵机能在 $f(n)$ 步之内停机；
NTIME($f(n)$) 的，如果求解规模为 $n$ 的问题的非确定性图灵机能在 $f(n)$ 步之内停机。

在此基础上，我们定义几个复杂度类：

$\mathbf{P} = \bigcup_{k \geq 1} \text{DTIME}(n^k)$；
$\mathbf{NP} = \bigcup_{k \geq 1} \text{NTIME}(n^k)$；
$\mathbf{EXP} = \bigcup_{k \geq 1} \text{DTIME}(2^{n^k})$；
$\mathbf{NEXP} = \bigcup_{k \geq 1} \text{NTIME}(2^{n^k})$。

空间复杂度¶

在这里，我们需要考虑的是图灵机的纸带花费多大的空间。我们同样定义一个问题是：

DSPACE($f(n)$) 的，如果求解规模为 $n$ 的问题的确定性图灵机花费 $f(n)$ 长度的纸带；
NSPACE($f(n)$) 的，如果求解规模为 $n$ 的问题的非确定性图灵机花费 $f(n)$ 长度的纸带。

定理（Savitch 定理） $$ \text{NSPACE}(f(n)) = \text{DSPACE}(f^2(n)) $$

这个估计的证明并不困难，图灵机有 $f(n)$ 个状态，非图灵机建图就是 $f^2(n)$ 级别的。类似地，我们定义：

$\mathbf{PSPACE} = \bigcup_{k \geq 1} \text{DSPACE}(n^k)$；
$\mathbf{NPSPACE} = \bigcup_{k \geq 1} \text{NSPACE}(n^k)$。

但是这个时候，Savitch 定理就告诉我们，$\mathbf{PSPACE} = \mathbf{NPSPACE}$。而由于确定性图灵机的对称性，我们也有 $\mathbf{co-PSPACE} = \mathbf{PSPACE}$。所以，空间复杂度层级中，$\mathbf{PSPACE}$ 就成为了几乎唯一最重要的一个。

当然，还有一些亚线性复杂度的问题，在此略过不表。

接下来，我们要考虑的就是空间复杂度和时间复杂度之间的关系。我们有：

\[ \mathbf{P} \subset \mathbf{NP} \subset \mathbf{PSPACE} \subset \mathbf{EXP} \]

P 问题¶

由多项式时间算法解决的问题集合。

其中多项式时间算法指的是算法的时间复杂度与输入的长度之间是多项式关系。

co-P 问题：补问题是 P 问题的集合（判断一个数是奇数 -> 判断一个数是偶数）

有：P = co-P.

NP 问题¶

NP(Non-deterministic Polynomial time)问题是指可以在多项式时间内验证一个解的问题集合。但是并不确定能不能在多项式时间内找到一个解。

co-NP 问题：

一个公式是否无论如何赋值，都是为真的（可用一个假公式来验证）

（补：一个公式是否存在一个赋值，是假的，可以用一个假公式来验证）
图不存在哈密顿路径

（补：图存在一条哈密顿路径）

NP-hard 问题¶

NP-hard 问题是指所有的 NP 问题都能在多项式时间内约化为该问题。NP-hard 问题不一定是 NP 问题,它是比 NP 问题更难的问题。

NPC 问题¶

NPC(NP-Complete) 问题是指既是 NP 问题，又是 NP 问题中最难的问题 (NP-hard)。如果能在多项式时间内解决一个 NPC 问题，那么所有的 NP 问题都能在多项式时间内解决。也就是说

P 问题能在多项式时间内解决，自然也能在多项式时间内验证，所以 P 问题是 NP 问题的子集；

NPC 问题是 NP 问题的子集；

NPC 问题也是 NP-hard 问题的子集；

NP-hard 问题不一定是 NP 问题

常见问题汇总¶

常见的 NPC 问题¶

可满足性问题 SAT：给定一个逻辑表达式，是否存在某种赋值让其为真
顶点覆盖问题：在图中，找到一个最小的顶点集合，使得该集合中的顶点能够覆盖图中的所有边
Clique（团）问题：无向图中找到一个完全子图，其中的每两个顶点都直接相连
哈密尔顿回路、哈密尔顿路径问题
Dominating Set 问题：在图中，找到一个最小的顶点集合，使得该集合中的每个顶点或者与之相邻的顶点都在集合中
Independent Set 问题：在图中，找到一个最大的顶点集合，使得该集合中的任意两个顶点都没有边连接
0-1 背包问题或者划分问题：在一个集合中寻找一个子集，让子集元素之和等于二分之一全集元素之和

常见的 NP-Hard 问题¶

旅行商问题：给定一系列城市和城市间的距离，求解遍历每个城市的最短距离的回路（没有负环依然是 NP-Hard）
最短路，带负环，而且要求是找到具有最短路的无环路径
装箱问题（NP-HARD）：给定 n 个物品，能否用 k 个箱子装下