NP完全问题

到现在为止我们讨论的问题都是面对一个问题如何设计出一个高效的算法。现在我们要讨论一个不同的问题，我们可以通过分析证明一些问题是不可能存在高效的算法的。而证明的方法依然是设计算法。

多项式时间复杂度是优秀的复杂度。确定型图灵机能在多项式时间复杂度内解决的问题的集合称为\(P\)，这里的P指polynomial time。非确定型图灵机能在多项式时间复杂度内解决的问题的集合称为\(NP\)。特别注意，\(NP\)不是指non polynomial，而是指non-deterministic polynomial time。普通计算机都是确定型图灵机，而“非确定型图灵机”在面临选择（比如搜索类问题）时能同时尝试“选”与“不选”。因此，非确定型图灵机能在多项式复杂度内解决的问题等价于确定型图灵机能在多项式复杂度内“验证”的问题。显然，\(P \subseteq NP\)。最著名的问题就是，是否成立\(P \subsetneq NP\)？或者说是否有\(P=NP\)？举个生动的例子，“不会做但能看懂答案的题”是否等价于“会做的题”？

我们讨论问题的难度：定义多项式时间图灵归约\(f \leq_T^P g\)，表示\(g\)是多项式复杂度的图灵机，能够用来解决\(f\)，同时要求\(f\)的运行步骤是多项式复杂度的，调用\(g\)的次数也是多项式（多项式乘以多项式依然是多项式）。如果存在一个\(g\)，使得对于所有\(NP\)问题\(f\)都有\(f \leq _T^P g\)，那么称\(g\)是一个NP-hard问题。注意NP-hard问题不一定是NP问题。如果\(f\)是NP-hard同时也是NP的，那么\(f\)被称为NP-complete问题。如果我们证明了一个NP-complete问题是能多项式解决的，就能证明\(P=NP\)。

SAT问题是一个NP-complete问题。合取范式(CNF)由若干个括号由\(\wedge\)连成，每个括号由布尔变量\(x_i\)或\(\neg x_i\)用\(\vee\)连成。比如\((x_1 \vee x_3 \vee \neg x_4)\wedge(x_2 \vee \neg x_3) \wedge(x_1 \vee x_2)\)。SAT问题就是，输入一个CNF，问是否存在一个\(x_1\)到\(x_n\)的赋值使得CNF的值为true。为什么SAT是NP-complete的证明比较复杂，简单来说就是如果存在多项式时间解决SAT的算法，那么我们就可以模拟非确定型图灵机。由于规约具有传递性，要证明某个问题\(f\)是NP-hard，只需证明SAT\(\leq_T^P f\)。

3-SAT问题是一个特殊的SAT问题，它要求输入的CNF的每个括号里都恰好只有3个布尔变量。显然有3-SAT\(\leq_T^P\)SAT，我们想证明SAT \(\leq_T^P\) 3-SAT。这里用到一个关键的技巧：当\(x_i\)任取时，一定存在一个\(y\)使得\((x_1 \vee x_2 \vee x_3 \vee x_4)=(x_1 \vee x_2 \vee y) \wedge (\neg y \vee x_3 \vee x_4)\)。如果\(y=0\)，那么RHS等价于\((x_1 \vee x_2)\)，如果\(y=1\)，那么RHS等价于\((x_3 \vee x_4)\)。意思是说，如果LHS=1，那么要么\(x_1,x_2\)中有1要么\(x_3,x_4\)中有1。对于前者，只需取\(y=1\)，对于后者，只需取\(y=0\)；如果LHS=0，只需取\(y=0\)，就有RHS=0。

一般地，一定存在一个\(y_i\)的取值使得：\((x_1 \vee x_2 \vee \cdots \vee x_k)=(x_1 \vee x_2 \vee y_1) \wedge (\neg y_1 \vee x_3 \vee y_2) \wedge (\neg y_2 \vee x_4 \vee y_3)\)\(\wedge \cdots \wedge (\neg y_{k-3} \vee x_{k-1} \vee x_k)\)。意思是说，如果LHS=1，那么分类讨论：如果\(x_1,x_2\)中有1，那么取\(y_1=0,y_i=0\)；如果\(x_3=1\)，那么取\(y_1=1,y_2=0,y_i=0\)；如果\(x_4=1\)，那么取\(y_2=1,y_1=1,y_3=0,y_i=0\)；如果\(x_p=1\)，那么取\(y_1\cdots y_{p-2}=1\)，\(y_{p-1}\cdots y_{k-3}=0\)；如果\(x_{k-1},x_k\)中有1，那么取\(y\)全都取1。如果LHS=0，那么只需取\(y_1=0\)，就有RHS=0。

于是对于任何SAT问题， 我们做这样的替换，就能把它转变成3-SAT问题。即SAT \(\leq_T^P\) 3-SAT。因此SAT等价于3-SAT。

SAT可以规约为图论中的独立集问题。图上没有互相连边的点的集合称为一个独立集。我们的问题是：给定一张图，问是否存在一个\(k\)个点的独立集。每个3-CNF（\(n\)个布尔变量，\(m\)个括号）对应着一张图，图上有\(2n\)个节点分别对应\(x_i\)与\(\neg x_i\)，将每个括号里的三个点连成三角形，再将所有\(x_i,\neg x_i\)之间相连。每个独立集里最多只能有每个三角形里的一个点，也不可能同时有\(x_i\)与\(\neg x_i\)。假如我们能在这张图里找到一个\(m\)个点的独立集，那么令这\(m\)个点对应的布尔变量取1，这就保证了3-CNF的每个括号里恰好有一个1，因此有SAT问题\(\leq_T^P\)独立集问题。因此独立集问题是一个NP-hard问题。

点覆盖是指选出一个点的集合，使得与这些点相连的所有边覆盖了整张图的所有边。任意取一个独立集，然后反向选择所有不属于独立集的点，这个点集构成\(S\)。假设存在一条边，它的两个端点都不在\(S\)中，那么说明这两个点都在独立集中，这是不可能的，因此\(S\)覆盖了所有边。任意取一个点覆盖，然后反向选择所有不属于点覆盖的点，这个点集构成\(W\)。假设存在一条边，它的两个端点都在\(W\)中，那么这两个端点都不在点覆盖中，这是不可能的，因此\(W\)是独立集。综上，假设存在一个\(u\)个节点的独立集，那么对应地一定存在一个\(n-u\)个节点的点覆盖。假设存在一个\(u\)个节点的点覆盖，那么对应地一定存在一个\(n-u\)个节点的独立集。因此，如果最大独立集是\(m\)，那么最小点覆盖就是\(n-m\)。

我们可以构造无向图\(G\)的补图\(G'\)：本来没边的都有边，本来右边的都没变（邻接矩阵取反）。一个Clique是指两两互相有边的点的集合。于是，\(G\)中的独立集一定是\(G'\)中的Clique，\(G'\)中的Clique一定是G中的独立集。于是\(G\)中的独立集与\(G'\)中的Clique一一对应，因此求\(G'\)的Clique等价于求\(G\)的独立集。所以有独立集问题\(\leq_T^P\)Clique问题。由规约的传递性得，SAT \(\leq_T^P\)Clique。因此Clique问题是NP-hard问题。

Half Clique询问是否存在一个\(|V|/2\)个节点的Clique。假设我们已经解决了Half Clique，现在要证明我们可以用它来解决Clique。假设询问的\(k< |V|/2\)，我们等价地考虑独立集。那么我们在原图的基础上新增\(|V|-2k\)个孤立的节点形成一张新的图。询问新图是否存在\(|V'|/2=|V|-k\)个点的独立集等价于询问原图是否存在\(|V|-k-(|V|-2k)=k\)个点的独立集，因此此时Clique问题可以规约为Half Clique的问题；假设询问的\(k \geq |V|/2\)，我们考虑Clique。那么我们在原图的基础上新增\(2k-|V|\)个孤立的节点形成一张新图。询问新图是否存在\(|V'|/2=k\)个节点的Clique等价于询问原图是否存在\(k\)个节点的Clique，因此此时Clique问题也可以规约为Half Clique问题。综上，由于(ii)已经证明了Clique问题是NP-hard，由规约的传递性可得Half Clique问题也是NP-hard。