Computational Complexity: Time Complexity 2

Diagonal Method:对角线方法

通用图灵机$\mathbb{U}(\alpha, x)$能够模拟$\mathbb{M} _\alpha (x)$的计算,因此,我们可以枚举每一个$\alpha$和$x$的编码,并制定如下所示的表:

1

Fig. 1. UTM

在上表中,每列从上到下枚举TM的编码 ,每行从左到右枚举输入$x$,使用UTM可以计算出每一格内的值。右表是一个假想的结果,其中$\uparrow$表示死循环。而这个表中,对角线上的值是一个特殊值,因为在对角线上,$\alpha=x$,即UTM计算的是$\mathbb{M} _\alpha(\alpha)$。利用对角线做反证法,可以证明很多有趣的结论,这就是所谓的对角线方法(Diagonal Method)。

通俗地来说,对角线方法就是用自己来推翻自己。

下面给出了两个应用对角线方法的案例。

UC:不可计算函数

定义函数:

$$
\text{UC}(\alpha) =
\begin{cases}
0,& \text{if}\space \mathbb{M} _{\alpha} (\alpha)=1\\
1,& \text{otherwise}
\end{cases}
$$

利用对角线方法可以证明上述函数是不可解的,也就是说没有图灵机能够求解该函数:

假设存在图灵机$\mathbb{W}$能够计算UC,那么我们有:
$$
UC(\alpha) = \mathbb{M} _{\llcorner \mathbb{W} \lrcorner}(\alpha)
$$
若:
$$
\mathbb{M} _{\llcorner \mathbb{W} \lrcorner}(\llcorner \mathbb{W} \lrcorner)=1
$$
则:
$$
UC(\llcorner \mathbb{W} \lrcorner)=\mathbb{M} _{\llcorner \mathbb{W} \lrcorner}(\llcorner \mathbb{W} \lrcorner)=0
$$
同理,若$\mathbb{M} _{\llcorner \mathbb{W} \lrcorner}(\llcorner \mathbb{W} \lrcorner)=0$,我们也会推出$\mathbb{M} _{\llcorner \mathbb{W} \lrcorner}(\llcorner \mathbb{W} \lrcorner)=1$。两者互相矛盾。
因此,不存在这么一个图灵机,也就是说UC是不可计算的。

HALT:停机问题

HALT,停机问题是这样定义的:

$$
\text{HALT}(\alpha,x) =
\begin{cases}
1,& \text{if}\space \mathbb{M} _{\alpha} (x)\space \text{terminates}\\
0,& \text{otherwise}
\end{cases}
$$

停机问题可以用UC函数来证明:

假设存在$\mathbb{M} _H$计算了停机问题,则对于任意的$\alpha$都有:
$$
\mathbb{M} _H(\alpha,\alpha)=\text{HALT}(\alpha,\alpha) =
\begin{cases}
1,& \text{if}\space \mathbb{M} _{\alpha} (\alpha)\space \text{terminates}\\
0,& \text{otherwise}
\end{cases}
$$
于是我们可以定义一个新的函数$\text{MU}(\alpha)$:
$$
\text{MU}(\alpha) =
\begin{cases}
0,& \text{if}\space \mathbb{M} _{H} (\alpha,\alpha)=1\space\&\space\mathbb{M} _{\alpha} (\alpha)=1\\
1,& \text{otherwise}
\end{cases}
$$
在上述函数的定义下,如果$\mathbb{M} _{\alpha} (\alpha)$停机了,那么其值要么是$1$,要么是$0$,其中$1$会使得$\text{MU}(\alpha)$输出$0$;如不停机,则$\text{MU}(\alpha)$会和$\mathbb{M} _{\alpha} (\alpha)$值为$1$一样输出$1$。换句话说,条件$ \mathbb{M} _{H} (\alpha,\alpha)=1$在$\text{MU}$中并不发挥作用,只要$\mathbb{M} _{\alpha} (\alpha)=1$,$\text{MU}(\alpha)$就只会输出$1$。于是:
$$
\text{MU}(\alpha) =\text{UC}(\alpha)
$$
而UC是不可计算的,所以上面的所有证明都不成立,所以不存在这么一个图灵机计算了停机问题。

停机问题不可计算说明,对于任意的图灵机$\mathbb{M} _\alpha$和输入$x$,在实际运行之前我们无法预先知道$\mathbb{M} _\alpha(x)$是否能停机。

实际上上面的证明还用了归约法(Reduction Method),即通过放宽判定条件,使得某一问题$q$成为另一个问题$Q$的子问题。此时我们若证明$Q$不可计算,那么$q$也就相应地无法计算了。

Speedup Theorem:加速理论

加速理论解决的是对于某个问题,是否存在最快的算法的问题。直觉告诉我们,这个答案是否定的,因为只要我们有足够的空间,我们就可以空间换时间,通过“打表”把每一种输入的答案都列举出来,那么对于所有的问题我们都可以用常量的时间解决。而实际上也正是如此,没有最快的算法,只有更快的算法(理论上)。

Blum’s Speedup Theorem是关于此的很强的一个结论,但它的具体内容和证明都比较复杂,课程中没有涉及,本文也只记录关于线性加速理论的内容。

Linear Speedup Theorem:线性加速理论

Hartmanis和Stearns于1965年证明了线性加速理论:

Linear Speedup Theorem:设图灵机$\mathbb{M}$在$T(n)$步内计算了$f$,任取$\epsilon > 0$,总存在图灵机$\mathbb{M}'$,它能在$\epsilon T(n)+n+2$步内计算$f$。

这里用到的方法是“压缩带子”,即通过编码,使得$\mathbb{M}'$上的一格能够记录$\mathbb{M}$上$m$格的内容,这样$\mathbb{M}'$的一步就相当于$\mathbb{M}$上的$m$步,其证明如下:

对于$\mathbb{M}(\Gamma,Q,\delta)$,用一个新的符号集$\Gamma '$为$\Gamma$中的$m$个字符用$1$个字符编码。不难看出,这样的符号集$\Gamma '$是巨大的,其字符种类至少为$|\Gamma '| > |\Gamma|^m$。我们用$\Gamma '$构建一个新的图灵机$\mathbb{M}'(\Gamma ',Q',\delta ')$,对该图灵机:

  • 使用与$\mathbb{M}$相同的带子数;
  • 对于$\mathbb{M}$纸带上长度为$n$的编码,$\mathbb{M}'$可以在$n+2$步内将其转换为$n/m$长的编码;(多出的2步是起始符和终止)
  • $\mathbb{M}'$在$n/m$步可以将所有的带头回归到原点;
  • $\mathbb{M}'$纸带上的任何一个格子对应着$\mathbb{M}$上的$m$个格子。某一时刻$\mathbb{M}$在$m$个格子内任意一个格子上的$m$步在$\mathbb{M}'$上至多会涉及到3个格子,因此$\mathbb{M}'$只需要记录下这三个格子的值、做一步写入操作、移动一次带头,至多5步就可以模拟$\mathbb{M}$上的$m$步。
    因此,总时间:
    $$
    n+2+\frac{n}{m}+5\frac{T(n)}{m}\le n+2 + \frac{6}{m}T(n)
    $$
    我们可以取$\epsilon=6/m$,$m=6/\epsilon$,证毕。

2

Fig. 2. 1 -> m

Time Complexity Class:时间复杂性类

对于语言L(即一个判定问题集合),如果存在图灵机$\mathbb{M}$和常数$c>0$,使得$\mathbb{M}$能在$cT(n)$的时间内判定L,那么我们说$L\subseteq \text{TIME}(T(n))$。换句话说,$\text{TIME}(T(n))$中的语言都具有$O(T(n))$的算法。

复杂性类(Complexity Class)是一些具有类似复杂度的问题的集合,或者说是一些具有类似复杂度解的问题的集合。因为对于大多数的问题,我们都能用简单或复杂的方法将其解出来,换句话说,我们不能定义问题的复杂性,我们只能定义解的复杂性。显然,上面提到的$\text{TIME}(T(n))$不是一个复杂性类,因为它是和模型相关的。比如,对于回文问题,我们可以在$O(n)$的时间内解决,此时回文问题在$\text{TIME}(n)$中,但我们也可以用$O(n^2)$的方法解决,此时回文问题在$\text{TIME}(n^2)$中。

下面给出一些常见的时间复杂性类,这里面就有之前提到的P、NP问题。

Complexity Class P

$\text{P}$类,即多项式类,所有具有多项式时间算法的问题都属于这一类:

$$
\text{P}=\bigcup _{c\ge 1}\text{TIME}(n^c)
$$

在承认强CT论题的情况下,$\text{P}$类是与模型无关的,也就是说它是一个复杂性类。

强CT论题(Strong Church-Turing Thesis):所有物理上可实现的机器都能在多项式的时间复杂度内被图灵机模拟。

Complexity Class EXP

$\text{EXP}$类,即指数时间复杂性类:

$$
\text{EXP}=\bigcup _{c\ge 1}\text{TIME}(2^{n^c})
$$

底数是无关紧要的,既可以是2,也可以是任何数字。出于规定,$\text{P}\subseteq\text{EXP}$,所以$n^c$不可以写成$cn$,否则集合内部的封闭性复合运算将不被满足。如:$n^3\in\text{P}$,所以$n^3\in\text{EXP}$,$2^n\in\text{EXP}$,那么将$n^3$和$2^n$复合得到的$2 ^{n^3}$理应也在$\text{EXP}$中。若将$n^c$写成$cn$则$2 ^{n^3}$将不被包含在$\text{EXP}$中,这显然是错误的。

Nondeterministic Turing Machine:非确定图灵机

非确定性图灵机(Nondeterministic Turing Machine)具有两个迁移函数$\delta _1,\delta _2$,它在运行过程中会随机地选择一个迁移函数来执行,并产生相应的结果。不难看出,NDTM的计算路径可以被视为一棵二叉树,叶子结点表示某一条会停机并产生结果的执行路径,有些路径可能无限长:

3

Fig. 3. DTM and NDTM

上述的非确定图灵机在物理上是无法实现的,而之前所提到的物理上可实现的图灵机都称为确定图灵机(Deterministic Turing Machine,DTM)。

Guessing:猜测

NDTM通常被用来解决存在性问题。事实上,对于输入$x$,NDTM的每一条计算路径都在试图构造或者猜测一个对$x$存在性的证明,若构造/猜测成功,则NDTM接受$x$,否则拒绝$x$。对于某一个决策问题或者语言,在NDTM中有如下规定:

  • 对于一台NDTM$\mathbb{N}$,当输入为$x$时,若$\mathbb{N}(x)$存在一条计算路径中止于接受格局(即$\mathbb{N}(x)=1$),则称$\mathbb{N}$接受$x$;否则若所有的计算路径都失败,则称$\mathbb{N}$拒绝$x$。
  • 对于一语言L,如果$x\in L$当且仅当$\mathbb{N}$接受$x$,则称$\mathbb{N}$接受L。

这实际上就是枚举,其中,有些解路径可能很短,能达到多项式的时间复杂度,而有些解路径可能很长,需要指数的时间复杂度。

Complexity Class NP & NEXP

类似于DTM,对于NDTM,我们也可以定义时间复杂性类:对于语言L(即一个判定问题集合),如果存在非确定图灵机$\mathbb{N}$和常数$c>0$,使得$\mathbb{N}$能在$cT(n)$的时间内判定L,那么我们说$L\subseteq \text{NTIME}(T(n))$。换句话说,$\text{NTIME}(T(n))$中的语言都具有$O(T(n))$的算法。

同样地,定义非确定多项式(Non-deterministic Polynomial)复杂性类$\text{NP}$:

$$
\text{NP}=\bigcup _{c\ge 1}\text{NTIME}(n^c)
$$

非确定指数复杂性类$\text{NEXP}$:

$$
\text{NEXP}=\bigcup _{c\ge 1}\text{NTIME}(2^{n^c})
$$

它们与DTM的关系为:

$$
\text{P}\subseteq\text{NP}\subseteq\text{EXP}\subseteq\text{NEXP}
$$

  • 第一、三层包含是因为DTM是NDTM的特例,即$\delta_1=\delta_2$;
  • 第二层包含是因为DTM可以用指数的时间将NDTM的所有路径走一遍。

$\text{NP}$和$\text{P}$的区别在于,$\text{P}$的解的复杂度都是多项式的,而$\text{NP}$只是存在多项式复杂度的特解。能否证明$\text{P}=\text{NP}$,是理论计算机科学界中的一大难题。

'Universal' Nondeterministic Turing Machine:“通用”非确定图灵机

一个“通用”的非确定图灵机$\mathbb{V}$在模拟某个时间复杂度为$T(n)$的图灵机$\mathbb{M}$时需要四条带子:

  1. 输入带;
  2. 存放snapshot的工作带,该工作带存放$\mathbb{V}$对$\mathbb{M}$执行时产生的所有snapshot的猜测,快照数为$O(T(n))$;
  3. 存放转移函数序列(即$01$串)的工作带,该工作带$01$串的长度也是$O(T(n))$,实际上就是$\delta_1$和$\delta_2$序列;
  4. 存放对被模拟工作带验证结果的工作带,它会记录一些snapshot,以验证对某个被模拟带子的模拟是否正确,若正确则清空,验证下一个带子。

快照个数$O(T(n))$,$01$串的个数也是$O(T(n))$,故模拟的时间复杂度也是$T(n)$。这是在正确猜测的情况下,但实际上猜测序列、快照不一定是正确的,$T(n)$也不一定时间可构造,所以这台“通用”的非确定图灵机甚至有可能不停机,故“通用”是带引号的。若$T(n)$时间可构造则可掐表,以确保$\mathbb{V}$会停机。

注意,以上的$T(n)$只对非确定图灵机的一条路径,即对非确定图灵机所“猜测”的任意一条路径,模拟它的时间复杂度可以到$T(n)$。

参考