【计算理论】07 时间复杂性与空间复杂性

概述

度量复杂度的目的在于，如果求解一个问题需要过量的计算资源（运算时间或者存储量），那么即使在理论上该问题可判定，该问题在实践上仍不可解。

在衡量时间/空间复杂度时，通常采用$O$表示法，表示复杂度的上界。

时间复杂度

定义：令$M$为在所有输入都停机的确定型图灵机，$M$的运行时间，或称时间复杂度，为函数$f:\mathcal{N}\to \mathcal{N}$，$f(n)$为在所有长度为$n$的输入上运行所经过的最大步数。

简单地说，就是在长度为$n$的字符串上，需要移动读写头多少步。

TIME类

例：分析判定语言 A = { 0 k 1 k ∣ k ≥ 0 } A = \{0^k1^k|k \ge 0\} A={0k1k∣k≥0}的算法。

解：图灵机章节提到过两种思路：第一种是一对一对置换0和1；第二种是折半方法，间隔一个置换，并比较奇偶性。由于这里的主要目的是进行算法分析，故不列出具体的证明，可以参看前面的笔记。

对于第一种构造方法，当判定长度为$n$的串时，每次都会删除一个0和一个1，最多需要$\frac{n}{2}$次扫描，每次扫描的需要$O(n)$步，因此第一种构造方法的时间复杂度为$O(n^2)$。

对第二种构造方法，当判定长度为$n$的串时，由于每次都会进行折半，可知需要进行$O(\log n)$次扫描，每次需要$O(n)$步，时间复杂度为$O(n\log n)$。

定义：令$t:\mathcal{N}\to {\mathcal{R}}^{+}$为一个函数，定义确定型时间复杂性类$TIME(t(n))$，为由$O(t(n))$时间内的图灵机判定的所有语言的集合。例如，$TIME(n^2)$包含所有能在$O(n^2)$内判定的语言。

若满足${?}_{k}TIME(n^k)$，则称多项式时间（polynormal time）。

模型复杂性关系

这段补充前后思路用的，没做要求。

考察单带图灵机、多带图灵机与非确定性图灵机的时间复杂度关系。

定理：设$t(n)$为一个函数，且$t(n)\ge n$。则每个$t(n)$时间的多带图灵机，都等价于一台$O(t^2(n))$的单带图灵机。

证明思路：在图灵机章节中，说明过如何将一台多带图灵机转换为单带图灵机，因此只需要说明这种模拟需要多少额外的时间即可。

证明：设$M$为在$t(n)$内运行的$k$带图灵机，构造等价的单带图灵机$S$模拟$M$的运行。

$S$在一条带子上表示$M$的所有带，为模拟$M$的一步，$S$需要扫描带上的所有信息，确定在$M$的读写头下的符号，然后再次扫描，更新带子内容和读写头位置。假设在$M$的运行中，$M$的读写头每步都向右移动，则$M$会用掉$t(n)$个格子，反映到$S$上，对应移动$t(n)$步，因此在$S$模拟$M$运行的每步，最多都需要$O(t(n))$步，且$M$需要运行$t(n)$步，因此总共需要的时间为$O(t^2(n))$步。

简要来说，$S$为了模拟多带图灵机，需要在$M$运行的每步都需要让读写头多跑很多路，多跑的这些路的上界为$t(n)$，也即$M$的最大带长。

定理：设$N$为非确定型图灵机，且是判定器。$N$的运行时间为$f:\mathcal{N}\to \mathcal{N}$，其中，$f(n)$为在任何长度为$n$的输入上所有计算分支中的最大步数。设$t(n)$为一个函数，且$t(n)\ge n$。则每个$t(n)$时间的非确定型单带图灵机，都与一个$2^{O(t(n))}$时间的确定型单带图灵机等价。

证明思路：证明该定理，可以将非确定型图灵机的推理过程理解为树状结构，在图灵机章节中，证明确定与非确定的等价性使用的是一台三带确定型图灵机来模拟非确定型图灵机，每次访问某个结点时，都会从根出发，下行到该结点。

证明：在长度为$n$的输入上，$N$的非确定型计算树的每个分支长度最多为$t(n)$，设每个节点最多有$b$个子，可知最多可能的叶子数为$b^{t(n)}$。

由于树的结点总数不超过叶子的两倍，故可用$O(b^{t(n)})$来表示结点数量的上界。由于计算分支的长度最多为$t(n)$，因此下行到每个结点的时间上界为$t(n)$。整理可知模拟$N$运行的图灵机的运行时间为$O(t(n)b^{t(n)})=2^{O(t(n))}$。

在图灵机章节的证明中，使用了一台三带图灵机来模拟非确定型图灵机的运行，从本节上一条定理可知，将多带转换为多带最多使运行时间乘方。所以转换为单带图灵机后，运行时间仍为$2^{O(t(n))}$。

从复杂性关系的证明可知，当度量时间复杂度时，确定型单带和多带图灵机的时间复杂度差异最多为平方或多项式差异；而对于非确定和确定型图灵机之间，差异最多为指数差异。

通常认为多项式差异是较小的差异，而指数差异是大的。典型的指数时间算法就是穷举整个搜索空间（即暴力搜索），而通过特定的设计，也许可以找到多项式时间运行的算法。

多项式时间通常作为实际可解性的标准。

P类

首先给出$P$类的定义
$$\begin{gathered} P类是确定型单带图灵机，在多项式时间内可判定的语言类，即: \\ P=\underset{k}{?}TMIE(n^k) \end{gathered}$$
P类问题通常对应于在计算机上实际可解的那些问题，且对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的。

下面给出P类问题的一些示例与其属于P类的证明，仍采用构造性证明的方法，构造能够在多项式时间内判定问题的判定机。

PATH问题

给出PATH问题的定义：
$$PATH=\{(G,s,t)|G为从s到t存在路径的有向图\}$$
证明思路：证明问题属于P类，只需要构造出能够在多项式时间内判定该问题的图灵机，并分析时间复杂性即可。

证明：构造图灵机$M$：
$$\begin{array}{l}M=\text{“对输入}(G,s,t):\\ 1.在t上进行标记;\\ 2.重复以下步骤，直到没有新的结点被标记:\\ a.标记所有能够到达已经被标记节点的未标记节点;\\ 3.若s被标记，则接受，否则拒绝。\text{”}\end{array}$$
在上式中，步骤2最多运行$m$次，每次需要遍历一遍所有结点，最坏条件下，每次新标记一个结点，故上述图灵机的时间复杂度为$O(m^2)$，为多项式时间；可知$PATH$问题为P类问题。

互素数（RELPRIME）问题

定义：
P E L P R I M E = { < x , y > ∣ x , y 是互素数 } PELPRIME = \{<x, y>| x, y是互素数\} PELPRIME={<x,y>∣x,y是互素数}
证明思路：辗转相除法，每次求模并互换。

证明：构造图灵机$M$：
$$\begin{array}{l}M=\text{“对输入}<x,y>,x,y是二进制表示的自然数:\\ 1.重复以下操作，直到y=0;\\ a.赋值x\leftarrow x\mathrm{mod}y;\\ b.交换x和y的值;\\ 2.输出x。\text{”}\end{array}$$
构造使用图灵机$M$的判定器$R$：
$$\begin{array}{l}R=\text{“对输入}<x,y>:\\ 1.在<x,y>上运行M;\\ 2.若M的结果为1，则接受；否则拒绝。\text{”}\end{array}$$
由于$x,y$是二进制表示的自然数，且该算法的时间复杂度主要与较大（也就是二进制串较长）的字符串有关。在每次相除，$x$至少减少一半，而折半对二进制来说，相当于减少一位，因此上述算法的时间复杂性为$O(n)$。

证明 A = { 0 n 1 n ∣ n ≥ 0 } ∈ P A = \{0^n1^n|n\ge 0\} \in P A={0n1n∣n≥0}∈P

证明：构造图灵机$T$：
$$\begin{array}{l}T=\text{“}对输入w:\\ 1.间隔一个0，将0置换为x；间隔一个1，将1置换为y;\\ 2.每轮置换结束后，检查0和1的奇偶性，若不一致，则拒绝;\\ 3.若01都只剩一个，则接受。\text{”}\end{array}$$
上述图灵机每次都会将序列长度折半，因此需要搜索$O(\log n)$次；每次扫描的时间复杂性为$O(n)$，故判定该问题的时间复杂性为$O(n\log n)$为多项式时间，得证$A\in P$

证明正则语言一定是P类

证明：构造图灵机$T$模拟DFA的运行：
$$\begin{array}{l}T=\text{“}对输入<M,w>:\\ 1.在w上模拟M的运行;\\ 2.若M接受，则接受，否则拒绝。\text{”}\end{array}$$
对长度为$n$的串，DFA每次都读取一个字符，对应有确定的状态转移，故模拟一台DFA运行的图灵机，需要运行$O(n)$步，为多项式时间。

NP 类

这段有点绕，慢慢来

在P类问题中，我们提到了一些在计算机上实际可解的问题，这些问题已经找到了能够多项式时间求解（Finding solutions）的算法。

与P问题不同，NP问题可能无法在多项式时间内求解；但如果给定一个解，NP问题能够构造验证机，并在多项式时间内验证该解（Check/Verify solutions）。

例如，在合数问题$COMPOSITES$中，可能很难找到快速的算法（只能暴力搜索），判定某个数是否为合数，但只要给出一个特定的解（因子），就可以在多项式时间内验证$x$是否为合数。

合数问题的定义：
C O M P O S I T E S = { x ∣ x = p q , ? s . t . ? p , q > 1 } COMPOSITES = \{x| x = pq,\ s.t.\ p,q>1\} COMPOSITES={x∣x=pq,?s.t.?p,q>1}

给出验证机（verifier）的定义：语言$A$的验证机为满足以下条件的算法$V$：
A = { w ∣ 对某个字符串 c ， V 接受 < w , c > } A = \{w|对某个字符串c，V接受<w, c>\} A={w∣对某个字符串c，V接受<w,c>}
仍然举合数问题的例子，验证该问题，只需给出特定的一对$pq=x$，因此$w=x$，$c=p,q$，$V$为乘法计算。只要能够确定给定的$pq=x$，则可验证$x$为合数。

验证机的运行时间是根据$w$的长度来度量的，如果某台验证机能够在$w$长度的多项式时间内运行，则称该验证机为多项式时间验证机。

定义NP是具有多项式时间验证机的语言类，可进一步证明：一个语言在NP中，当且仅当它能够被某个非确定型多项式时间图灵机判定

证明：等价性证明证两边。

正向，设存在$A$的多项式时间验证机$V$，设$V$在$n^k$的多项式时间内运行，构造$N$：
$$\begin{array}{l}N=\text{“}对长度为n的输入w:\\ 1.非确定地选择最长为n^k的字符串c;\\ 2.在输入<w,c>上运行V;\\ 3.若V接受，则接受，否则拒绝。\text{”}\end{array}$$
反向，设$A$能够被多项式时间$NTMN$判定，构造$V$：
$$\begin{array}{l}V=\text{“}对输入<w,c>:\\ 1.在输入w上模拟N，将c的每个符号看作对N进行非确定性选择的描述;\\ 2.若N的该计算分支接受，则接受;否则拒绝。\text{”}\end{array}$$

综上，可给出使用$NTM$定义的NP问题，其时间复杂性类为$NTIME$，即非确定型时间复杂度：
N T I M E ( t ( n ) ) = { L ∣ L 为被 O ( t ( n ) ) 时间的非确定型图灵机判定的语言 } NTIME(t(n)) = \{L|L为被O(t(n))时间的非确定型图灵机判定的语言\} NTIME(t(n))={L∣L为被O(t(n))时间的非确定型图灵机判定的语言}
进而可以写出NP的形式化表述
$$NP=\underset{k}{?}NTIME(n^k)$$

给出从多项式时间验证机到等价多项式时间$NTM$的转化：

构造$NTMN$
$$\begin{array}{l}N=\text{“对长度为}n的输入w:\\ 1.非确定地选择最长为n^k的串c;\\ 2.在<w,c>上运行V;\\ 3.若V接受，则接受，若V拒绝，则拒绝。\text{”}\end{array}$$

证明问题属于NP问题，既可以构造多项式时间运行的非确定型图灵机，也可以构造多项式时间的验证机

HAMPATH问题

定义：
H A M P A T H = { < G , s , t > ∣ G 是包含从 s 到 t 的哈密顿路径的有向图 } HAMPATH = \{<G, s, t>| G是包含从s到t的哈密顿路径的有向图\} HAMPATH={<G,s,t>∣G是包含从s到t的哈密顿路径的有向图}

哈密顿路径即通过每个结点恰好一次的有向路径。

证明：构造非确定型图灵机$N$：
$$\begin{array}{l}N=\text{“}对输入<G,s,t>，G为包含结点s,t的有向图:\\ 1.非确定的挑选序列p_1,p_2,\dots ,p_m;\\ 2.在序列中检查重复性，如果有重复，则拒绝;\\ 3.检查p_1=s,p_m=t，若不成立，则拒绝;\\ 4.对从1到m?1的每个i，检查是否存在对应的边，不存在则拒绝;\\ 5.若所有检查通过，则接受。\text{”}\end{array}$$

上述图灵机的每步都能够保证在多项式时间内运行，故HAMPATH问题属于NP问题。

COMPOSITES问题

定义：
C O M P O S I T E S = { x = p q , ? s . t . ? p , q > 1 } COMPOSITES = \{x = pq, \ s.t.\ p, q > 1\} COMPOSITES={x=pq,?s.t.?p,q>1}
证明：构造验证机$V$，以$c=p,q$为证书。
$$\begin{array}{l}V=\text{“}对输入<x,<p,q>>:\\ 1.计算x=pq是否成立;\\ 2.若成立，则接受，若不成立，则拒绝。\text{”}\end{array}$$

CLIQUE问题

首先给出团的定义：定义无向图中的$k$团为无向图中$k$个结点的子图，且这$k$个结点两两相连。

进而给出CLIQUE问题的定义：
C L I Q U E = { < G , k > ∣ G 为包含 k 团的无向图 } CLIQUE = \{<G, k>|G为包含k团的无向图\} CLIQUE={<G,k>∣G为包含k团的无向图}
证明：构造验证机$V$，以符合条件的$k$团为证书
$$\begin{array}{l}V=\text{“}对输入<<G,k>,c>,c为满足条件的k团:\\ 1.检查c中的k个结点是否都是G中的结点;\\ 2.检查c中的结点是否在G中存在两两相连的边;\\ 3.若上述两项检查都通过，则接受，否则拒绝。\text{”}\end{array}$$

SUBSET-SUM问题

定义：
S U B S E T ? S U M = { < s , t > ∣ s 为数集 { x 1 , … , x m } , 且 s 存在子集 { y 1 , … , y l } ? s , 使得 ∑ y i = t } SUBSET-SUM = \{<s, t>|s为数集\{x_1, \dots, x_m\}, 且s存在子集\{y_1, \dots, y_l\} \sube s, 使得\sum y_i = t\} SUBSET?SUM={<s,t>∣s为数集{x1?,…,xm?},且s存在子集{y1?,…,yl?}?s,使得∑yi?=t}
证明：构造验证机$V$，以符合条件的子集为证书
$$\begin{array}{l}V=\text{“}对输入<<s,t>,c>:1.检查c中的数是否都来自s;\\ 2.检查c中数字的和是否等于t;\\ 3.若上述两项检查都通过，则接受，否则拒绝。\text{”}\end{array}$$

多项式时间可归约

在可归约性章节，我们提到了映射可归约的概念：若存在可计算函数$f:{\Sigma }^{?}\to {\Sigma }^{?}$，使得$?w\in A?f(w)\in B$，则称语言A映射可归约到B，记为
$$A{\le }_{m}B$$

类似的，可以定义多项式时间映射可归约，简称多项式时间可归约：若存在多项式时间可计算函数$f:{\Sigma }^{?}\to {\Sigma }^{?}$，使得$?w\in A?f(w)\in B$，则称语言A多项式时间可归约到B，记为
$$A{\le }_{p}B$$
多项式时间可归约符合映射可归约的相关性质，例如，若$A{\le }_{p}B$，且$B\in P$，则可知$A\in P$。证明的方法也是类似的

证明：设能够在多项式时间判定$B$的图灵机为$M$，构造能够在多项式时间内判定$A$的图灵机$T$：
$$\begin{array}{l}T=\text{“}对输入w:\\ 1.计算f(w);\\ 2.在f(w)上模拟M的运行，并输出M的输出。\text{”}\end{array}$$

在这里补充一些可判定可归约的构造思想，在DFA, CFG的大部分判定例子中，使用的是映射可归约的正向定理：若$A{\le }_{m}B$，且$B$可判定/可识别，则$A$可判定/可识别。此时需要将待证问题归约到已知问题，例如使用$A_{DFA}$作为子程序，构造$A_{NFA}$的判定器；以及使用$E_{DFA}$作为子程序，构造$E{Q}_{DFA}$的判定器。

而在$TM$判定性问题的例子中，使用的是上述定理的逆否命题：若$A{\le }_{m}B$，且$A$不可判定，则$B$不可判定。此时需要将已知问题归约到待证问题，即将$HALTTM,E_{TM}$等归约到$A_{TM}$，构造$A_{TM}$的判定器，再利用反证的思想来证明。

NP 完全

阐述NP完全性的目的是为了便于阐明P与NP的关系，NP完全问题可以被看作是NP类中的一个代表，如果能够证明$P=某个NP完全问题$，就可以得证$P=NP$；同样的，如果能够证明$P\ne 某个NP完全问题$，就可以得证$P<NP$。

给出NP完全的定义：若语言B满足以下条件，则称B为NP完全的：
$$\begin{array}{l}1.B\in NP;\\ 2.?A\in NP,A{\le }_{p}B.\end{array}$$
NP完全性具有传递性：若$B,C\in NP$，且$B{\le }_{p}C$，如果$B$是NP完全的，则$C$也是NP完全的。

证明：已知$B$为NP完全，则有
$$?A\in NP,A{\le }_{p}B{\le }_{p}C$$
满足条件2，又因$C\in NP$满足条件1，故$C$也是NP完全的。

NP完全其实还有挺多内容，例如找到第一个NP完全问题（SAT），并使用这个问题归约出其他NP完全问题，也很有意思。

考试没要求，这里就先跳过了。

空间复杂度

空间复杂度考试要求很少，很多内容没讲到，比较可惜。

对确定型图灵机来说，其空间复杂度为在长度为$n$的输入上扫描带子的最大方格数；

对非确定型图灵机来说，其空间复杂度为任何计算分支上扫描带子的最大方格数。

给出空间复杂性类$SPACE(f(n))$和$NSPACE(f(n))$的定义：
S P A C E ( f ( n ) ) = { L ∣ L 为被 O ( f ( n ) ) 空间的确定型图灵机判定的语言 } N S P A C E ( f ( n ) ) = { L ∣ L 为被 O ( f ( n ) ) 空间的非确定型图灵机判定的语言 } SPACE(f(n)) = \{L|L为被O(f(n))空间的确定型图灵机判定的语言\}\\ NSPACE(f(n)) = \{L | L为被O(f(n))空间的非确定型图灵机判定的语言\} SPACE(f(n))={L∣L为被O(f(n))空间的确定型图灵机判定的语言}NSPACE(f(n))={L∣L为被O(f(n))空间的非确定型图灵机判定的语言}

复杂性类之间的关系

萨维奇定理是空间复杂性最早的结论之一，该定理表明，确定型图灵机，可以使用非常少的空间，模拟非确定型图灵机的运行。该定理的结论为：对任何函数$f:\mathcal{N}\to {\mathcal{R}}^{+},f(n)\ge n$，有
$$NSPACE(f(n))?SPACE(f^2(n))$$
通过该定理，可证明$PSPACE=NPSPACE$

参照P与NP的定义，可以给出PSPACE的定义
$$PSPACE=\underset{k}{?}SPACE(n^k)$$
根据萨维奇定理可知，$NSPACE(f(n))?SPACE(f^2(n))$由于多项式的平方仍然是一个多项式，且确定型图灵机可被视为一种特殊的非确定型图灵机，易知$NPSPACE=PSPACE$。

进一步，考察时间复杂度类与空间复杂度类之间的关系，对一台在$t(n)\ge n$的时间上运行的机器，最坏情况下，该机器每步都会访问一个新的格子，因此这台机器的空间复杂性上界为$O(t(n))$，可知$P?PSPACE,NP?NPSPACE$，又因$PSPACE=NPSPACE$，结合时间复杂性的一些证明，可得到
$$P?NP?PSPACE=NPSPACE?EXPTIME$$

PSPACE完全

与NP完全的定义类似，PSPACE完全的定义为：若语言B满足以下条件，则称B为PSPACE完全的：
$$\begin{array}{l}1.B\in PSPACE;\\ 2.?A\in PSPACE,A{\le }_{p}B\end{array}$$
该定义也存在传递性，可参考NP完全传递性给出证明。

参考

• 《计算理论导引》第二版，机械工业出版社