Computational Complexity: Time Complexity 3

Time Hierarchy Theorem：时间谱系理论

理论：如果$f$和$g$都是时间可构造的，且$f(n)\log f(n)=o(g(n))$，则$\text{TIME}(f(n))\subsetneq\text{TIME}(g(n))$。

小o表示算法运行时间的严格上限，$f=o(g)$表示$f$运行的上限是$g$，换句话说，$f$的运行时间比$g$增长得慢。

该理论表明若$g$的运行时间增长快于$f\log f$运行时间的增长，则$f(n)$时间内能接受的语言是$g(n)$时间内能接受语言的子集。该理论的证明如下：

要证明$\text{TIME}(f(n))\subsetneq\text{TIME}(g(n))$，只要反证$\text{TIME}(g(n))\subsetneq\text{TIME}(f(n))$不成立即可。也就是说只要找到一个语言L，$L\in\text{TIME}(g(n))$，但是$L\notin\text{TIME}(f(n))$即可。

假设存在TM $\mathbb{D}$，它接受语言L，并且：

• 对于输入$x$，$\mathbb{D}$模拟$\mathbb{M} _x(x)$运行$g(|x|)$步（这是可行的，因为$g$是时间可构造的）；
• 如果模拟可以在$g(|x|)$步内完成（即停机），则$\mathbb{D}(x)$输出$\overline{\mathbb{M} _x(x)}$，否则输出$0$（$1$也行，不影响）。
  按照这样定义，$\mathbb{D}$会在$g(|x|)$停机，因此$L\in\text{TIME}(g(n))$。

此时再假设$L\in\text{TIME}(f(n))$，且图灵机$\mathbb{M} _z$在至多$2f(n)$内接受L。由于图灵机编码的任意性，取足够长的$z$，使得$f(|z|)\log f(|z|)< g(|z|)$严格成立，则会出现：

• $\mathbb{D}(z)=\mathbb{M} _z(z)$，因为$\mathbb{D}$和$\mathbb{M} _z$都接受L；
• $\mathbb{D}(z)=\overline{\mathbb{M} _z(z)}$，因为$\mathbb{M} _z(z)$可被通用图灵机在$O(f(|z|)\log f(|z|))$的时间内模拟，而$\mathbb{D}(x)$会模拟$\mathbb{M} _z (z)$进行$g(|x|)$步，又$f(|z|)\log f(|z|)< g(|z|)$严格成立，所以在$\mathbb{D}(x)$模拟$\mathbb{M} _z (z)$进行的$g(|x|)$步内，$\mathbb{D}(x)$已经停机，即$\mathbb{D}(z)=\overline{\mathbb{M} _z(z)}$。

上述结论相互矛盾，原假设不成立，$L\notin\text{TIME}(f(n))$。证毕。

上面的证明用到了对角线方法。

由时间谱系定理：

$$
\begin{align*}
\text{EXP}=&\bigcup _{c\ge 1}\text{TIME}(2^{n^c}) \\
\text{2EXP}=&\bigcup _{c\ge 1}\text{TIME}(2 ^{2^{n^c}}) \\
\vdots
\end{align*}
$$

存在严格的包含关系，即$\text{EXP}\subset \text{2EXP}...$

Nondeterministic Time Hierarchy Theorem：非确定时间谱系理论

理论：如果$f$和$g$都是时间可构造的，且$f(n+1)=o(g(n))$，则$\text{NTIME}(f(n))\subsetneq\text{NTIME}(g(n))$。

设有非确定图灵机$\mathbb{Z}$，只要证明$\mathbb{Z}$判定的语言L在$\text{NTIME}(g(n))$但不在$\text{NTIME}(f(n))$中即可。$\mathbb{Z}$的定义如下：

1. 只处理长度大于1的全1串$1 ^n$；
2. 输入带和第一条工作带同步地移动，第一条工作带在第一个工作区写入1，然后在后续的工作区中持续写入0，期间偶尔写入1；
3. 用$h _0, h _1...$记录下所有写有1的工作区的下标；
4. 在第二条工作带上，枚举所有的和时钟$2f(n)$硬连接的非确定图灵机NDTMs（的编码），记这些图灵机为$\mathbb{L} _1,\mathbb{L} _2...$；
5. 在生成非确定图灵机$\mathbb{L} _i$后，$\mathbb{Z}$模拟计算$\mathbb{L} _{i-1}(1 ^{h _{i -1}+1})$，并将结果（0或1）写入第二条工作带上，同时，在第一条工作带的$h _i$位置写上1。

   注意，因为$h _0=1$，所以$\mathbb{L} _0(1 ^{h _0+1})$是一开始就可以确定的，不需要等第一条工作带运行。
   $\mathbb{L} _{i-1}(1 ^{h _{i -1}+1})$中的$\mathbb{L} _{i-1}$和$1 ^{h _{i-1}+1}$都通过回溯之前的历史得到，回溯的时间复杂度为$O(n)$，因为$h _{i -1}$是单调递增的，故只需要局部回溯。而$\mathbb{L} _{i-1}(1 ^{h _{i -1}+1})$则用新的工作带（写入$\mathbb{L} _{i-1}$与$1 ^{h _{i-1}+1}$）、草稿带来计算（在$2f(n)$必内停机）。

$\mathbb{Z}$的输出规定为：

1. 如果在输入串$1 ^n$扫描结束时，最新的$h _i = n$且$\mathbb{L} _{i-1}(1 ^{h _{i -1}+1})=0$，则$\mathbb{Z}$接受$1 ^n$；
2. 反之如果$h _{i-1} < n < h _i$，则$\mathbb{Z}$模拟$\mathbb{L} _{i-1}$以非确定图灵机的方式计算$1 ^{n+1}$$g(n)$步，并以其结果作为最后的输出。

矛盾性的证明：

假设语言L被$\mathbb{Z}$接受：

• 则L$\in \text{NTIME}(g(n))$，因为$\mathbb{Z}$运行的时间复杂度只由完全扫描完输入后的计算时间决定，而输出规定2可在$g(n)$时间内完成（输出规定1为常量时间）。

再假定$\exists \mathbb{L} _i$在$f(n)$时间内接受L。于是，因为$f(n+1)=o(g(n))$，所以输出规定2中$\mathbb{Z}$对$\mathbb{L} _i$（此处的$i$指输入扫描结束后计算的最后一个$h$的前一个）的模拟可以被完成。故，由于$\mathbb{L} _i$和$\mathbb{Z}$都接受L：
$$\mathbb{L} _i(1 ^{h _i + 1})=\mathbb{Z}(1 ^{h _i + 1})$$
又由输出规定2：对输入串的长度$m= h_i+1$，$\mathbb{Z}$的输出结果与$\mathbb{L} _i(1 ^{m+1})=\mathbb{L} _i(1 ^{h _i + 1+1})$的结果相同：
$$\mathbb{Z}(1 ^{h _i + 1})=\mathbb{L} _i(1 ^{h _i + 2})$$
又由两者都接受L：
$$\mathbb{L} _i(1 ^{h _i + 2})=\mathbb{Z}(1 ^{h _i + 2})$$
若输入长度一直这样增加下去，则总会有一个时刻，$h _i +k=h _{i+1}$，此时：
$$\mathbb{L} _i(1 ^{h _{i+1}})=\mathbb{Z}(1 ^{h _{i+1}})$$
若$n=h _{i+1}$，则由输出规定1：
$$\mathbb{Z}(1 ^{n})=\mathbb{Z}(1 ^{h _{i+1}})\ne \mathbb{L} _i (1 ^{h _i+1})$$
出现矛盾，因此不存在这样的$\mathbb{L} _i$在$f(n)$时间内接受L。证毕。

Gap Theorem：间隙定理

描述：对任何一个可计算函数$r(x)\ge x$，一定存在一个可计算函数$b(x)$，使得$\text{TIME}(b(x))=\text{TIME}(r(b(x)))$。

时间谱系定理告诉我们$\text{TIME}(n ^c)\subsetneq \text{TIME}(2 ^{n ^c})$。而间隙定理说明，并不是对所有的$b(n)$，$\text{TIME}(b(n))\subsetneq \text{TIME}(2 ^{b(n)})$都成立，即有可能$\text{TIME}(b(n))=\text{TIME}(2 ^{b(n)})$。证明如下：

• 定义一个$r(x)\ge x$，以及$[0,r(k _x)]$上的$x+1$个不相交区间$[k _0, r(k _0)],...,[k _x, r(k _x)]$，其中：
  $$
  \begin{align*}
  k _0=&0 \\
  k _{i+1}=& r(k _i)+1,i < x
  \end{align*}$$
• 再定义$P(i,k)$为：对所有的$j \le i$及其编码的图灵机$\mathbb{M} _j$，对长度为$i$的字符串输入$z$，若$\mathbb{M} _j(z)$在$k$步内停机或者在$r(k)$步仍未停机，则$P(i,k)=\text{True}$；否则$P(i,k)=\text{False}$。

对这些图灵机$\mathbb{M} _0,...,\mathbb{M} _i$，它们能够接受总输入个数为：
$$n _i=\sum ^i _{j=0}|\Gamma _j| ^i$$
因此它们的运行时间有 $n _i$种可能。而$[0,r(k _{n _i})]$上有$n _i+1$个不相交区间$[k _0, r(k _0)],...,[k _{n _i}, r(k _{n _i})]$。也就是说，总会有那么几个区间，在这些区间，没有任何的$\mathbb{M} _j(z)$运行步数在它们的范围内。换句话说，在这些区间的左端点$k _m$上，$P(i,k _m)$是$\text{True}$的。
由此，我们可以定义一个函数$b(i)$，对任何一个$i$，它的值是这些区间中的某一个的左端点，即$b(i)=k _m$。于是我们有$P(i,b(i))$对于所有的$i$都成立。

• 进一步地，假设$\mathbb{M} _j$在$r(b(n))$的时间内接受L。

则对于任何的输入$x$，若其长度$n \ge j$，由$P(n,b(n))=\text{True}$，我们有：
$\mathbb{M} _j(x)$要么在$b(n)$步内停机，要么$r(b(n))$步还不停机。
然而，$\mathbb{M} _j$在$r(b(n))$的时间内接受L，所以$\mathbb{M} _j(x)$在$r(b(n))$步内一定已经停机，所以$\mathbb{M} _j(x)$在$b(n)$步内停机，所以$\mathbb{M} _j$在$b(n)$的时间内接受L，所以：
$$\text{TIME}(b(n))=\text{TIME}(r(b(n)))$$

我们可以确保$b(n)$和$r(b(n))$满足$f(n)$和$g(n)$的大小关系，因为$r(x)$可以是任意的，只要$r(x)\ge x$即可。但$b(n)$却不满足时间谱系定理，这说明这样的$b(n)$是时间不可构造的。