02 时间复杂性

如何定义时间复杂性

加速定理(Speedup Theorem)

当我们提到“时间复杂性”的时候，我们说的是“一个算法的时间复杂性”，这是通过这个算法在图灵机上的运行步数来定义的。但有时候我们会说“一个问题的复杂性”，例如排序问题的复杂性是$O(n\log n)$，这是因为我们证明了不可能有一个算法能比这更快的解决排序问题， 换言之排序问题是有“最优算法”的。

那么，是不是所有问题都有最优算法呢？答案是否定的，我们不加证明的给出Blum加速定理的叙述：存在一个问题$f:\{0,1\}^*\to\{0,1\}^*$，对于任意能计算$f$的图灵机$M_i$（假设$M_i(x)$的运行步数为$T_i(x)$），可以找到另一台能计算$f$的图灵机$M_j$使得$r(T_j(x))<T_i(x)$关于$x$几乎处处成立，其中$r$是可以任意选取的一个单调函数。这里的“几乎处处成立”的意思是只对有限个$x$不成立。这个定理告诉我们，存在这样的问题，我们永远可以找出复杂性更优的算法，因此不存在复杂性最优的算法。例如取$r(n)=2^n$，假设$f$有一个$O(T)$的算法$M_i$，那么$2^{T_j}<T_i$，所以存在一个$O(\log T)$的算法。

Blum加速定理意味着，对问题定义复杂性将不会是良定义的。我们只能对算法定义复杂性，不能对问题定义复杂性。

线性加速定理(Linear Speedup Theorem)

下面这个线性加速定理告诉我们，我们的确不需关心复杂性中的常数。为了方便，我们只讨论判定问题。对于一个判定问题，假设存在一个$T(n)$步内计算它的图灵机$M_i$，那么可以构造一个$M_j$只需$\epsilon T(n)+n+2$就可以计算这个问题，其中$\epsilon$是任选的正实数。要做到这一点，只需扩充图灵机$M_j$中的符号集：设$M_i$的符号集大小为$|\Gamma|$，对于$\Gamma$中符号连成的长度为$m$的符号串，我们可以用一个大小为$|\Gamma|^m$的新符号集$\Gamma'$编码所有这些符号串，这样在用$M_j$模拟$M_i$时，$M_i$的$m$步操作只需在$M_j$上对应常数$c$步，因此$\epsilon$可以取$\dfrac{c}{m}$，可以任意小。

这告诉我们，编程时可以使用更高阶的指令集（更高级的程序语言），从而实现常数优化。因此以后在讨论复杂性问题时，我们都可以使用大$O$符号，避开对常数的讨论。

复杂性类(Complexity Classes)

为了讨论方便，接下来我们提到“问题”时指的都是判定性问题，也即只要求输出一个bit的问题。尽管并不是所有问题都可以归约成判定性问题，但我们将会看到判定性问题已经极具代表性了。

尽管我们不能对问题定义“复杂性”，但我们可以根据问题已有的最优算法的复杂性对问题进行分类。然而如何划分复杂性类并不是一个显然的问题。以“回文串判定”问题为例，假设在一台多带图灵机上，它有$O(n)$算法；但是如果规定图灵机只有一条纸带（令输入带不为只读，这也是一个计算模型），那么可以证明不存在$O(n)$算法，因为读写头必须来回移动，最优复杂度也会达到$O(n^2)$。这个例子说明，“一个问题是否有$O(n)$算法”是依赖于具体的计算模型的，而不是模型无关的。因此，我们不应当定义一个$O(n)$复杂性类。

多项式类和指数类

加强版的丘奇-图灵命题说，任何物理过程的计算都可以在图灵机上用多项式倍的复杂度来模拟。也即假设一个计算过程需要$T$步，那么一定可以在某台图灵机上用$O(T^C)$步来模拟，$C$是常数。这同样是人们的一种信仰，而不是一个定理。如果相信这一加强版的丘奇-图灵命题成立，那么“多项式类”$P=\bigcup\limits_{C\geq 1}\text{TIME}(n^C)$就是一个良定义的复杂性类：任何物理上需要多项式步的计算，在图灵机上也只需要多项式步。所以人们通常把多项式复杂度的算法称为高效(efficient)的算法。

同样的，还可以定义指数复杂性类$\text{EXP}=\bigcup\limits_{C\geq 1}\text{TIME}(2^{n^C})$。（注意不是$2^{Cn}$）

非确定性图灵机

还有一类问题，能够有多项式复杂度的验证算法，但不一定有多项式复杂度的判定算法。例如，要判定图上是否存在一个大小为$k$的独立集，假设已经给出了一个解，那么只需验证这些点两两间是否右边，因此能$O(|V|^2)$判定；但是人们到目前为止还没找到多项式复杂度的算法来判定是否存在解，只能$O(2^{|V|})$暴力枚举。我们想为这类问题也定义一个复杂性类。

我们能否为“多项式复杂度可判定”这一描述定义一个具体的计算模型呢？我们可以定义一个称为“非确定性图灵机(Non-Deterministic Turing Machine, NDTM)”的模型。普通的图灵机模型称为确定性图灵机，它每运行一步会修改读写头上的符号，并将读写头移动一格。我们可以把运行一步前后图灵机发生的变化看作一个状态转移函数$\delta$，确定性图灵机每一步运行都是按照状态转移函数的规则转移一次。对于非确定性图灵机，我们定义它有两个状态转移函数$\delta_1,\delta_2$。非确定性图灵机每运行一步，会分别尝试使用$\delta_1$和$\delta_2$，从而得到了两个不同的状态，我们认为这两个状态同时存在。接下来再运行一步，会得到四个状态同时存在。运行$n$步，会得到$2^n$个状态的叠加态。如果这$2^n$个状态中有一个状态是满足要求的输出，非确定性图灵机就运行结束，因为这意味着我们已经可以用这个特定状态对应的那$n$步状态转移构造一个确定性图灵机的算法来检验了。例如，我们可以构造这样的非确定性图灵机来解决$k$-独立集判定问题。每运行一步，我们加入图上的一个新的点，创造选它与不选它的叠加态。在运行了$|V|$步以后，已经有了$2^{|V|}$个状态，对应着图的所有点集，此时判断这些点集是否有一个大小为$k$的独立集即可。

我们找不到多项式复杂度内模拟非确定性图灵机的确定性图灵机。换言之， 根据强丘奇-图灵命题，非确定性图灵机并不是物理上能够实现的计算模型。它是我们为了描述“多项式可验证”这一性质而构造出来的一个数学意义上的计算模型。

定义非确定性图灵机在多项式步运算内能判定的问题集合为$NP=\bigcup\limits_{C\geq 1}\text{NTIME}(n^C)$。这等价于所有存在多项式复杂度验证算法的问题集合。

显然，一个多项式时间可判定的问题肯定是多项式时间可验证的。所以$P\subseteq NP$。迄今为止，人们还没能证明是否有$P=NP$或$P\neq NP$。

Time Hierarchy Theorem(时间谱系定理)

显然，假设时间函数满足$f(n)\leq g(n)$，那么一定有$\text{TIME}(f(n))\subseteq \text{TIME}(g(n))$。我们想问，当$f(n)$和$g(n)$的大小关系满足什么样的条件时，这种包含关系会是严格的呢？时间谱系定理回答了这个问题：当$\lim\limits_{n\to\infty}\dfrac{f(n)\log f(n)}{g(n)}=0$时，有$\text{TIME}(f(n))\subsetneq \text{TIME}(g(n))$。

对这一定理的证明再次用到了对角线方法。我们可以构造这样一个判定性问题$L(x)$，使得$L\in \text{TIME}(g(n))$却不满足$L\in\text{TIME}(f(n))$。$L(x)$定义如下：当输入$x$时，用通用图灵机模拟图灵机$M_x(x)$，若$g(|x|)$步后通用图灵机停机，则输出$M_x(x)$的取反，如果不停机就输出0。根据定义，显然$L \in \text{TIME}(g(n))$。然而假如$L \in \text{TIME}(f(n))$，那么存在一台图灵机$M_z$，在输入$z$后能在$O(f(|z|))$内输出$M_z(z)=L(z)$。通用图灵机模拟$M_z(z)$只需不超过$O(f(|z|)\log f(|z|))$步，因此$L(z)$一定会输出$M_z(z)$取反，与$L(z)=M_z(z)$矛盾。因此$L\not\in \text{TIME}(f(n))$。

因此，时间谱系定理告诉我们当允许的计算时间提高一个量级以后，能计算的问题一定会变得更多。问题与问题间可以划分出严格的谱系：一定有这样的问题，能在$O(2^{n^c})$下计算而不能在$O(n^c)$下计算；也一定有这样的问题，能在$O(2^{2^{n^c}})$下计算而不能在$O(2^{n^c})$下计算……

同样运用对角线方法，还可以对于非确定性图灵机证明类似的结论：当$\lim\limits_{n\to\infty}\dfrac{f(n+1)}{g(n)}=0$时，有$\text{NTIME}(f(n))\subsetneq \text{NTIME}(g(n))$。

Gap Theorem(间隙定理)

我们注意到，Time Hierarchy Theorem要求时间函数必须是时间可构造的。我们现在可以给出一个时间不可构造的函数，它能打破Time Hierarchy Theorem的陈述$\text{TIME}(f(n))\subsetneq \text{TIME}(g(n))$。下面的定理称为Gap Theorem：

对于任意可计算的全函数$r(x)$（我们要求$\forall x,r(x)\geq x$），存在可计算的全函数$b(x)$使得$\text{TIME}(b(x))=\text{TIME}(r(b(x)))$成立。

$Proof.$

我们构造一个函数$b$，使得$\text{TIME}(b(x))=\text{TIME}(r(b(x)))$成立。显然，$\text{TIME}(b(x))\subseteq$ $\text{TIME}(r(b(x)))$，因此只需证$\text{TIME}(r(b(x)))\subseteq \text{TIME}(b(x))$。即证对于任意$L\in \text{TIME}(r(b(x)))$，成立$L\in \text{TIME}(b(x))$。也即存在图灵机$\mathbb{M}$使得$\exists X,\forall x>X$，$\mathbb{M}$能在$Cb(x)$步内判定$L(x)$。（这里之所以可以转化为“对于充分大的$x$”，是因为我们可以取充分大的常数$C$）

我们按编码枚举前$i+1$台图灵机$\mathbb{M}_0,\cdots,\mathbb{M}_i$，设$\mathbb{M}_i$的符号集为$\Gamma_i$，那么能在所有这些图灵机上输入的长度为恰好为$i$的符号串总数为$n_i=\sum\limits_{j=0}^{i}|\Gamma_j|^i$。对于任意给定的$r(x)$，令$k_0=0$，$k_{i+1}=r(k_i)+1$。注意到，$k_0,k_1,\cdots,k_t$是一个单调递增的数列，他们把整数划分成了连续的闭区间$[k_0,r(k_0)],[k_1,r(k_1)],\cdots,$ $[k_t,r(k_t)]$。对于任意一台图灵机$\mathbb{M}_j,0\leq j \leq i$，它在接收一个长度不超过$i$的输入$z$时，最多只会有$n_i$种不同的运算表现，因此其停机步数至多只有$n_i$个不同的值。于是取$t=n_i$，根据鸽巢原理在上述$n_i+1$个闭区间里至少有一个不包含任何可能的$\mathbb{M}_j(z)$的运行步数，也即“对于任意$|z|=i$，存在$0\leq s\leq n_i$（如果有多个就取最小的那个），要么$\mathbb{M}_j(z)$在$k_s$步以内停机，要么$\mathbb{M}_j(z)$在$r(k_s)$步以后才停机”。这一命题对于任意$i$以及任意$j<i$都成立。我们令$b(i)=k_s$，这样就完成了$b$的构造。下面验证这一构造满足定理的要求。

因为$L\in \text{TIME}(r(b(x)))$，所以存在图灵机$\mathbb{M}_g$能在$O(r(b(x)))$步以内判定$L(x)$。对于任意输入$x$，只要$|x|\geq g$，就有：要么$\mathbb{M}_g(x)$在$b(x)$步以内停机，要么$\mathbb{M}_g(x)$在$r(b(x))$步以后才停机。我们总可以取到一个足够大的$X$，使得$x>X$时$b(x)$足够大，此时我们总是可以认为$\mathbb{M}_g(x)$在$b(x)$以内停机了。因此$L\in \text{TIME}(b(x))$。

$Qed.$

可见，由于在Gap Theorem中$r$可以是任意的，所以$b$不可能是时间可构造的，否则就与Time Hierarchy Theorem相矛盾。这样我们就给出了第一个时间不可构造的函数的例子。

正是因为Gap Theorem，讨论时间不可构造的时间函数的复杂性类就失去了意义。因此在计算复杂性理论中，我们一般只关注时间可构造的时间函数。