[Theoretical Computer Science] 算法以及复杂性

我们如何定义一个程序的运行时间？为了排除“不同计算机”的运行速度对时间的影响，我们将一个程序的运行时间定义为“一个固定计算模型上单位操作的次数”，这个固定的计算模型一般指图灵机。

程序的运行时间与输入规模有关，也与程序采用的算法有关。同样规模的输入，由于其数据可能具有不同的“性质”，也会导致程序运行的时间有所不同。因此，我们用时间复杂度的概念来描述程序对于输入规模（比如\(n\)）在最坏情况下的运行时间。

我们关心复杂度的级别而不是复杂度的细节，因此我们引入高阶无穷大中的记号：

如果\(T(n),g(n)\)在\(n \to \infty\)时有\(\dfrac{T(n)}{g(n)} \leq C\)（有上界），就记\(T(n)=O(g(n))\)。其中\(g(n)\)是我们的一个标尺，对于多项式可以取\(n,n^2\cdots\)。如果取\(g(n)=n^2\)，那么形如\(T(n)=n^2,2n^2,5n^2+7n+9,n,2n+3,1\)的复杂度都可以被记为\(T(n)=O(n^2)\)，意思是\(T(n)\)不会超过\(g(n)\)这个级别，\(T(n)=n^3\)就不满足\(T(n)=O(n^2)\)。总之，\(O(g(n)) \leq C \cdot g(n)\)。

如果\(T(n),g(n)\)在\(n \to \infty\)时有\(\dfrac{T(n)}{g(n)} \geq C\)（有下界），就记\(T(n)=\Omega(g(n))\)。如果取\(g(n)=n^2\)，那么形如\(T(n)=n^2,2n^2,5n^2+7n+9,n^3,2^n\)的复杂度都可以被记为\(T(n)=\Omega(n^2)\)，意思是\(T(n)\)至少有\(g(n)\)这个级别，\(T(n)=n,1\)等就不满足\(T(n)=\Omega(n^2)\)。总之，\(\Omega(g(n)) \geq C \cdot g(n)\)。

如果又有\(T(n)=O(g(n)),T(n)=\Omega(g(n))\)，那么就记\(T(n)=\Theta(g(n))\)。如果取\(g(n)=n^2\)，那么形如\(T(n)=n^2,2n^2,5n^2+7n+9\)的复杂度都可以被记为\(T(n)=\Theta(n^2)\)，意思是\(T(n)\)正好就是\(g(n)\)这个级别，\(T(n)=n,n^3\)等都是不满足\(T(n)=\Theta(n^2)\)的。\(\Theta\)是一种精确的描述。总之，\(C_1 \cdot g(n) \leq \Theta(g(n)) \leq C_2 \cdot g(n)\)。

举个例子来分析算法的时间复杂度：求\(n\)个数中的第\(k\)小。一种思路是，每次找最小然后删除，复杂度\(O(n^2)\)；一种思路是，先排序然后取第\(k\)个，复杂度\(O(n\log n)\)。有一个称为“中位数的中位数”的算法，首先把整个数组五个五个分组，求出每组的中位数，复杂度\(O(n)\)；再求出这些中位数的中位数\(v\)，这是一个递归的问题，假设整个问题的时间复杂度为\(T(n)\)，那么这一步耗费\(T(\dfrac{n}{5})\)；把所有小于\(v\)的数放进集合\(L\)，所有大于\(v\)的数放进集合\(R\)，等于\(v\)的放进集合\(M\)，耗费\(O(n)\)；此时我们发现，在这\(\dfrac{n}{5}\)个中位数中，比\(v\)小的那些中位数所在的每个组里至少有三个比\(v\)小，比它大的也是如此。也就是说，至少有\(\dfrac{n}{2} \cdot \dfrac{3}{5}\)个数比\(v\)小，有\(\dfrac{n}{2} \cdot \dfrac{3}{5}\)个数比\(v\)大。因此有\(\dfrac{3}{10}n \leq |L|,|R| \leq \dfrac{7}{10}n\)。因此递归到\(L,R\)的复杂度不超过\(T(\dfrac{7}{10}n)\)。综上，算法的复杂度可以写成递归表达式：\(T(n)=T(\dfrac{n}{5})+T(\dfrac{7n}{10})+O(n)\)。我们把\(O(n)\)写作\(Cn\)的形式：\(T(n)=T(0.2n)+T(0.7n)+Cn\)，递归地展开，最终\(T\)的项会趋向0，而带有\(Cn\)的项形成了等比数列\(T(n)=Cn+0.9Cn+0.9^2Cn+\cdots\)，因此\(T(n) \leq 10Cn\)，得到了\(T(n)=O(n)\)。

多项式时间复杂度是优秀的复杂度。确定型图灵机能在多项式时间复杂度内解决的问题的集合称为\(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。