NP-完全问题

算法导论

这个文档是学习“算法设计与分析”课程时做的笔记，文档中包含的内容包括课堂上的一些比较重要的知识、例题以及课后作业的题解。主要的参考资料是 Introduction to algorithms-3rd(Thomas H.)（对应的中文版《算法导论第三版》），除了这本书，还有的参考资料就是 Algorithms design techniques and analysis (M.H. Alsuwaiyel)。

NP-完全问题

在之前介绍的问题中，有些问题能够在较低次数(e.g. 3)的多项式时间内解决，而有些问题则是无法使用高效的算法解决。此外，这些问题也不太可能在未来某天找到高效的算法进行求解。

令 \(\Pi\) 表示任何一个问题，称存在一个多项式时间的算法解决问题 \(\Pi\) 当且仅当存在一个时间复杂度问题 \(O(n^k)\) 算法求解问题 \(\Pi\)，其中 n 为输入的长度，k 为一个非负整数。

然而有趣的是，在现实世界中，大多数问题并不属于这个分类，因为求解这些问题的算法的时间复杂度都是指数甚至是超指数的，e.g.\(2^n, n!\) 。

因此在计算机科学中，将那些存在多项式时间算法求解的问题称为易驾驭的(tractable)，而那些不可能找到一个多项式时间复杂度算法求解的问题称为棘手的(intractable)。

这里将会介绍棘手问题的一个子类，被称为NP-完全问题(NP-complete Problems)。

在研究NP-完全理论(Theory of NP-completeness)的时候，通常会将问题重申为一个决策问题(decision problem)，也就是这个问题的解只能是yes或者no，与之形成对比的就是优化问题(optimization problem)，也就是与某个数量的最小化或者最大化相关的问题，比如找到列表中的最小数或者最大数，又或者最小生成树问题。

下面介绍一个例子，令 S 为一个实数序列，那么问题 ELEMENT UNIQUENESS 问题就是关心 S 中的所有数字是否都是不同的。

将这个问题改写为决策问题，则

决策问题: ELEMENT UNIQUENESS
输入: A sequence S of integers.
问题: S 中是否有两个相等的元素？

将这个问题改写成优化问题，那么就是关心序列 S 中出现频率最高的元素，如下：

优化问题: ELEMENT COUNT
输入: A sequence S of integers.
输出: S 中出现频率最高的元*.

如果能够一个高效的算法解决一个决策问题，那么也能很容易找到该问题对应的优化问题。

比如下面这个问题，给定一个无向图 G = (V, E)，为图中每个节点使用 k 种颜色中的一种着色，要求邻接的节点不同使用相同的颜色，那么着色问题是指，是否能够用一个指定数目的颜色数为一个无向图着色。决策问题如下：

决策问题: COLORING
输入: 无向图 G = (V,E) 以及一个正整数 k ≥ 1
问题: 图 G 是否是能够k-着色的? 也就是说是否能够最多使用 k 中颜色为图 G 着色?

这个问题是棘手的(intractable)，如果令 k = 3，那么这个问题就是著名的3-着色问题，即使当 G 是一个平面图也是棘手的。

这个问题的优化问题是，用上述的方法对一个图进行着色所需的最小颜色数，记为\(\chi(G)\)，如下：

优化问题: CHROMATIC NUMBER
输入: 无向图 G = (V,E).
输出: 图 G 的着色数.

那么，如果能够一个高效的算法 A 解决图着色的决策问题，那么就可以利用算法 A 以二分搜索法来找到图 G 的着色数：显然 \(1\le\chi(G)\le n\)，那么就在这个区间内找到一个数 k，满足A(k) = yes, A(k-1) = no，这样只需要调用 \(O(\log n)\) 次算法 A 就能得到图G的着色数。

因为这个原因，在研究NP-完全问题时，通常更加关注决策问题。

P 类问题

确定性算法：令 A 表示解决问题 \(\Pi\) 的一个算法，称算法 A 是确定的，如果在问题 \(\Pi\) 的一个实例中，算法在执行的每一个步骤中都只有一个选择，因此，使用相同的输入实例运行算法 A 时，其输出不会改变。

有了确定性算法的定义后，就可以定义P类问题：

P类问题：如果一个决策问题的解能够通过一个确定性算法在多项式 \(O(n^k)\) 个步骤中得到，其中 n 为输入的规模，k 为一个非负整数，那么就称这个问题是 P 类问题。

比如排序问题：
SORTING: 给定一个包含 n 个整数的序列，判断这个序列是否是以非递减(nodecreasing)的顺序排序的？

如果对于任何问题 \(\Pi\in C\)，\(\Pi\) 的补集也在 C 中，那么就称 C 类问题在补集下是封闭的(closed under complementation)。

P类问题在补集下都是封闭的，比如上面的SORTING问题。

NP 类问题

NP类问题是指，存在一个确定性算法 A，能够在多项式时间内验证这类问题的解。

为了定义NP类问题，这里先介绍非确定性算法的定义，对于一个输入 x，非确定算法通常由两个阶段组成：

1. guessing phase: 这个阶段会生成一个任意的字符串 y，这里的“任意”是指这个字符串可能对应输入实例的解，也可能不对应，甚至可能不满足问题解的格式。
   非确定性算法的不同运行可能会得到不同的字符串。而对这个字符串唯一的要求是要能够在多项式个步骤中生成这样的字符串，即\(O(n^i)\) 个步骤中，其中 \(n = |x|\) 而 i 是一个非负整数。
2. verification phase: 在这个阶段，使用一个确定算法验证两件事：首先，验证前一步生成的字符串 y 是否是满足问题解的格式，如果不满足，那么算法输出 no 并终止。
   否则，算法进一步验证 y 是否是问题的解，如果是，那么就输出 yes 并终止，否则输出 no 并终止。要求这一步也能在多项式时间 \(O(n^j)\) 内完成，其中 j 为一个非负整数。

令 A 为问题 \(\Pi\) 的一个非确定算法，称 A 接受(accepts)了问题 \(\Pi\) 的一个实例 I 当且仅当，算法 A 对于输入I，能够在某次猜测中得到 yes 的答案。

这里需要强调的是，如果非确定算法 A 对于输入 I 输出了答案 no 也并不意味着算法 A 不接受实例 I，而是算法 A 可能猜测了一个不正确的解。

NP类问题：如果一个决策问题存在一个运行在多项式时间的非确定算法，那么这个问题就是NP类问题。

P类问题和NP类问题有下面两点区别：

• P类问题是指能够通过运行在多项式时间内的确定算法决策或者解决的决策问题；
• NP类问题是指能够通过运行在多项式时间内的确定算法验证该问题的解的决策问题；
  或者等价的，NP类问题是指能够通过运行在多项式时间内的非确定算法解决的决策问题。

也就是说，可以有两种方法证明一个问题属于NP类问题。

NP-complete

术语“NP-完全”(NP-complete)代表NP类问题中最难的那部分决策问题，也就是说，如果能够证明NP-完全问题中的某个问题是能够通过运行在多项式时间内的确定算法解决的，那么所有的NP类问题都能够通过一个运行在多项式时间内的确定算法解决，也就是说 NP = P，然而到目前为止，还没有人能够证明 NP = P，也就是说证明一个NP-完全问题能够在多项式的时间内求解。

而这里主要是介绍如果证明一个问题是NP-完全问题。

多项式规约：假设有两个决策问题 \(\Pi,\Pi'\)，如果存在一个多项式时间的确定算法 A，A 能够将问题 \(\Pi\) 的实例 I，转换成为问题 \(\Pi'\) 问题的实例 I'，并且对问题 I 的解为 yes 当且仅当对问题 I' 的解也为yes。 那么就称问题 \(\Pi\) 能够多项式规约到问题 \(\Pi'\)，记为\(\Pi\propto_{poly} \Pi'\)。

NP-hard：对于一个决策问题 \(\Pi\)，如果有 \(\forall \Pi'\in NP, \Pi'\propto_{poly} \Pi\) ，则称问题 \(\Pi\) 是NP-hard 的。

NP-complete：对于一个决策问题\(\Pi\)，如果有 \(\forall \Pi'\in NP,\Pi'\propto_{poly}\Pi\)，且\(\Pi\in NP\)，则称问题 \(\Pi\) 是NP-complete的。

The satisfiability problem

这是一个著名的NP-完全问题，给定一个布尔表达式 f，如果 f 是多个子句的合取(conjunction)，而每个子句是多个布尔变量或布尔变量取反的析取(disjunction)，称这个表达式是CNF(Conjunctive Normal Form)范式。比如下面这个例子：
\(f=(x_1\lor x_2)\land (\bar{x_1}\lor x_3\lor x_4\lor \bar{x_5})\land (x_1\lor \bar{x_3}\lor x_4)\)

称一个CNF范式是可满足的，如果存在对范式中的布尔变量的某中赋值方式使得该范式为真，比如上面例子中的CNF中令 \(x_1,x_3\) 为真，则范式也为真，所以上面的CNF范式是可满足的。

决策问题: SATISFIABILITY
输入: 一个CNF布尔公式 f
问题: f 是否是可满足的？

可满足性问题是第一个被证明为NP-完全的问题，而作为第一个NP-完全问题，也没有别的NP-完全问题能够多项式归约到这个问题上。所以这个问题的NP-完全性的证明是通过证明所有NP问题能够多项式归约到这个问题上，也就是说所有的NP问题都能够通过调用多项式确定算法 A 求解，其中算法 A 将可满足性问题作为其子程序，并且只调用一次这个子程序。

The proof consists of constructing a boolean formula f in conjunctive normal form for an instance I of Π such that there is a truth assignment that satisfies f if and only if a nondeterministic algorithm A for the problem Π accepts the instance I. f is constructed so that it “simulates” the computation of A on instance I.

CNF可满足性问题的证明过程也蕴含了一些基本定理，下面将会介绍。

NP-完全性的证明

多项式规约的关系是可传递的(transitive)，这对于NP-完全性的证明是有必要的。

定理：令 \(\Pi, \Pi'\) 以及 \(\Pi''\) 为三个决策问题，如果满足 \(\Pi\propto_{poly}\Pi',\Pi'\propto_{poly}\Pi''\)，则有 \(\Pi\propto_{poly}\Pi''\)。

证明略，可参考 Algorithms Design Techniques and Analsis。

推论：令 \(\Pi,\Pi'\) 为两个NP问题，如果有 \(\Pi'\propto_{poly}\Pi\)，并且 \(\Pi'\) 是NP-完全的，那么 \(\Pi\) 也是NP完全的。

证明略，可参考 Algorithms Design Techniques and Analsis。

所以通过上面的推论，如果要证明一个问题 \(\Pi\) 是NP-完全的，那么就需要证明：

1. \(\Pi \in NP\)
2. \(\exists\Pi'\in NP-complete,\Pi'\propto_{poly} \Pi\)

下面看一个例子，考虑下面两个问题：

1. Hamiltonian 回路问题：给定一个无向图 G = (V, E)，是否存在一个Hamiltonian回路，即能够访问图中每一个节点一次的回路?
2. 旅行售货员问题：给定一个集合的城市，以及每个城市间来往的距离，以及一个整数 k，是否存在一个仅访问每个城市一次的回路，并且回路的距离不超过 k?

现在已知Hamiltonian回路问题是NP-完全问题，现在要证明旅行售货员问题是NP-完全的。

#1. 首先需要证明旅行售货员问题是NP类问题。

这个比较容易证明，可以构造一个非确定性算法，首先生成一个任意城市的序列，然后验证这个序列是否是满足要求的，即按照序列的顺序能访问到每个城市一次并回到起点，然后再验证这个序列中城市间路径的长度是否是小于 k。

这样一个算法的时间复杂度显然是多项式时间以内的，于是可以得到一个多项式时间的非确定算法来解决这个问题。因此旅行售货员问题是NP类问题。

#2. 其次要证明Hamiltonian回路问题能够多项式归约到旅行售货员问题上，即：
\(HAMILTONIAN\_CYCLE\propto_{poly}TRAVELING\_SALESMAN\)

令 G = (V, E) 是Hamiltonian回路问题的任意一个实例，构造一个带权重的图 G' = (V, E') 以及一个边界 k 满足这样的条件：G 有一个Hamiltonian回路当且仅当 G' 有一个长度不超过 k 的访问路径，能够访问每个节点仅一次且回到起点。

构造 G' = (V, E') 如下：
\(E'=\lbrace (u,v)|u,v\in V \rbrace\)
并为每条边分配长度如下：
l(e) = 1 , if \(e\in E\)
l(e) = n , if \(e\notin E\)
其中 n = |V|，并且设定 k = n。

那么显然，G 中有一个Hamiltonian回路当且仅当 G' 中有一个长度刚好为 n 的访问路径，这个访问路径能够访问 V 中每个节点仅一次且返回起点。

这里需要强调的是，对 k 的赋值也是多项式规约的一部分。

显然，上面的规约步骤能够在多项式时间内完成，所以Hamiltonian回路问题能够多项式归约到旅行售货员问题上，因此旅行售货员问题是NP-完全问题。