算法导论随笔(十四)：NP完全性之P问题、NP问题、NPC问题和NP难问题

这篇文章中我来简单谈谈NP完全性。不同于前面所有文章中的各个具体的问题和算法，NP完全性是一个很抽象的大概念，其包括但不仅限于标题中提到的P问题、NP问题、NPC问题和NP难问题。这里我简单谈谈我对书上的内容和一些例子的理解。

P问题

首先来谈谈P问题。算法导论随笔系列写到现在，已经介绍了很多问题及它们的算法。其中大部分的问题，都是P问题。那么什么是P问题呢？P问题指的是能在多项式时间内解决的问题。这里的P是Polynomial（即多项式）的缩写。初中数学告诉我们，一个多项式有如下的形式：

其中a₀，a₁，… a_n为常数，n为常数。
也就是说，对于一个解决P问题的算法，其时间复杂度应该符合上述形式。比如冒泡排序的复杂度为
T(n) = O(n²)
这里的n²就是一个关于n的多项式。像冒泡排序这样复杂度可以表示为多项式的算法，就是多项式时间算法。如果一个问题能用多项式时间算法解决，那么这个问题就是P问题。书中的叙述也印证了我们的想法：

The class P consists of those problems that are solvable in polynomial time. More specifically, they are problems that can be solved in time O(n^k) for some constant k, where n is the size of the input to the problem.

并不是所有的算法都是多项式时间的。比如一个算法的复杂度为O(2ⁿ)，那么这个算法就不是多项式时间算法，因为多项式的形式中，每一项的指数应该是一个常数，而这里的指数为n，是一个变量，因此2ⁿ并不是一个关于n的多项式，也就是说复杂度为O(2ⁿ)的算法并不是多项式时间算法。再比如复杂度为O(n!)，或复杂度为O(nⁿ)的算法都不是多项式时间算法。

NP问题

下面来谈谈NP问题。先来看下面的一个问题：假设我们有一个如下图所示的Graph，其中每一个顶点代表一个城市，每条边上面的数字代表了两个城市之间的距离。现在有一个快递员要给图中所有的城市送快递，问什么路径可以访问所有的城市，并且快递员行走的距离之和最短。

这就是著名的旅行商问题。旅行商问题不是P问题，因为人们没办法找到一个多项式时间的算法来解决它。那么这个问题是不是NP问题呢？答案是不是。很多人觉得P问题的集合和和NP问题的集合互为补集，即一个问题若不是P问题，则它就是NP问题。这是一个误区，在后面会介绍。

既然旅行商问题不是P问题，也不是NP问题，那么为什么要在NP问题的小节中引入呢？答案是，虽然旅行商问题不是NP问题，但我们可以在旅行商问题的基础上提出一个NP问题。比如，我们问自己这样一个问题：在上面的图中，是否存在一条路径，其访问了所有的城市，并且路径的距离之和小于或等于15？

这个问题依然很难，那么我们可以换个思路。我们先蒙一条路径，比如上图中标粗的路径，其距离之和正好等于15。因此这个问题的解就得出来了，答案是存在。如果有人问我们为什么存在，那么我们就可以告诉他，因为我们找到了一条路径符合题目要求。在这道题中，找一个解很困难，但验证一个解只需要很短的时间，也就是说，我们可以在多项式时间内验证这个解。像这类能在多项式时间内验证的问题，被称为NP问题。

可以看出，所有的P问题都是NP问题。原因很简单，对于P问题，我们已经可以在多项式时间内解决它，那么我们也一定可以在多项式时间内验证一个解。比如数组排序，我们用一个排序算法在多项式时间内就可以将一个数组排序，那么我们也一定可以在多项式时间内验证一个给定的排序是正确的，因为我们最多也只需要把排序算法输出的正确结果和给定的结果进行比较即可：若它们相同则证明给定排序是正确的，若不同则证明给定排序是错误的。

那么所有的NP问题是否也都是P问题呢？这就是著名的P=NP问题。数学家和计算机科学家们一直试图证明P=NP，但目前并没有任何证据表明P=NP。所以，当前P与NP的关系为包含关系，如下图所示。

NPC问题

上文说到，科学界一直试图证明P=NP，但一直未能如愿。而导致他们相信P≠NP的最重要的一个因素就是NPC（NP-complete，NP完全）问题。原因是，NPC类问题有一个特点：即如果任何一个NPC问题能在多项式时间内解决，那么NP中的每一个问题都可以在多项式时间内解决。因此，只要找到NPC问题的多项式解法，就可以证明P=NP。然而，尽管经过这么多年的研究，人们仍然没有找到NPC的多项式时间算法。这也就导致了人们为什么相信P≠NP。

在讨论NPC问题之前，我们先来了解一个概念，即归约。简单地说，一个问题A可以归约为问题B的定义是，可以用问题B的解法解决问题A。也就是说，问题A可以“变成”问题B。书上对这个定义举了一个非常清晰的例子，比如二元一次方程
a x 2 + b x + c = 0 ax^2 + bx + c = 0 ax2+bx+c=0
可以归约为一个一元一次方程，只要我们把二次项系数a设置为0即可，即
0 x 2 + b x + c = 0 0x^2 + bx + c = 0 0x2+bx+c=0
那么我们就可以说，可以使用二元一次方程的解法来解决一元一次方程，因此一元一次方程可以归约成为二元一次方程。

若一个问题A可以归约为问题B，则我们说问题B至少和A一样难，并且可能比A还难。上述例子中，问题A就是一元一次方程，问题B就是二元一次方程。显然，二元一次方程要比一元一次方程难解。

那么如果我们能找到一个n元一次方程的解法，也就意味着我们找到了所有m元一次方程（m < n）的解法。NPC就是运用了这种思想：如果所有的NP都可以归约成一类问题，而我们找到了这类问题的多项式时间解法，那么我们就可以找到所有NP问题的多项式时间解法， 也就证明了P=NP。这一类问题，就是NPC问题。换句话说，NPC问题可以理解为科学家们为了证明或证伪P=NP时创造的一套理论。

我们可以这样理解NPC的定义：如果一个问题Q是NP问题，并且所有的NP问题都可以归约成Q，则Q是NPC问题。

下面举一个例子来说明NPC问题，即布尔电路可满足性问题。该问题是NPC问题。只要了解与运算、或运算和非运算，就不难理解布尔电路。布尔电路由与门、或门、非门构成。下图中a表示非门，b表示与门，c表示或门。

那么对于下图中的布尔电路，是否有一组x1，x2和x3的输入，使得最后的结果为1呢？
扩展到一般情况，给定任意一个布尔电路，是否存在一组输入使得最后得到的结果为1？这就是布尔电路可满足性问题，是一个NPC问题。

书中证明它是NPC的问题非常复杂，这里不再赘述，不过其思想大概可以理解为，任何一个NP问题，其实我们把它输入到计算机中，都是会转换成0和1的二进制码（比如数字在内存中直接以0和1存储，而字符以ASCII码进行存储，而ASCII码本质也是数字）。也就是说，不论是什么问题（简单起见，这里我们认为所有的问题都是判定问题，即问题的解为“是”或者“否”，比如“是否存在一条路径满足旅行商问题”），在计算机看来都是一串0和1的输入，而计算机给出的解不是0就是1。

那么这样看起来，这些问题就和布尔电路满足性问题非常类似，而实际上它们也确实都可以归约为布尔电路的满足性问题。又因为布尔电路满足性问题是NP问题，因此它满足NPC问题的定义，所以它是NPC问题。

NP难问题

NP难问题（NP-hard）是一类非常难的问题。它的定义比NPC问题少了一个条件，即它不一定是NP问题。也就是说，对于一个NP难问题，我们非但没办法找到多项式时间的解法，甚至没办法在多项式时间内验证它的解。比如上文中提到的“是否有一条路径长度小于等于15，且覆盖所有城市”是一个NP问题，但如果我们把问题改成“是否不存在一条路径长度小于等于15，且覆盖所有城市”，那么它就是一个NP难问题，因为除非我们遍历所有的路径，否则我们不能说“不存在这样的路径”。那么这样的话我们就没办法在多项式时间内验证一个解。因此这个问题是NP难问题。

P问题、NP问题、NPC问题和NP-hard问题的关系

上述四类问题的关系可以用下面的韦恩图表示。

我们可以看出，P是NP的子集，而NPC是NP和NP-hard的交集。也就是说，如果一个NP-hard问题同时又是一个NP问题，那么该问题就是NPC问题。