理论计算机科学基础随堂笔记。第7章：时间复杂性
使用教材：《计算理论导引》（原书第3版） Michael Sipser 著，机械工业出版社
目录
1、基本的复杂性度量；2、常见的时间复杂性类；3、P与NP问题。
第7章-1 时间复杂性
7-1.1 基本的复杂性度量
7-1.1.1 可计算与可有效计算
求解一个问题，可能有限步内可以完成，可能无限步才能完成。对于有限步可解决的问题，求解的步数与问题规模可能呈多项式关系，也可能呈指数级关系。
有限：effective, recursive, decidable, computable…
无限：ineffective, nonrecursive, undecidable, uncomputable…
多项式：polynomial, easy, efficient, tractable, feasible…
指数：exponential, hard, inefficient, intractable, infeasible…
如果一个问题有对应算法，它是可计算的(computable)；如果一个问题有多项式时间的算法，它是可以有效计算的。
为什么多项式函数受到青睐？直观地看，因为它花费时间随问题规模的增长比较慢，或者说指数时间的算法随问题规模增长过快，可能需要运行过长的时间，那就不是一个有效的算法。
多项式函数的特点：① 稳定。两个多项式函数求和、求积、做复合之后还是多项式函数；② 与指数函数相比，分析$n^k$和$c^n$。机器速度提高2倍后，前者同样时间内可求解问题的规模扩大了$^k\sqrt{2}$倍，而后者仅扩大到了$n+log_c2$，几乎可以认为可求解问题的规模没有扩大。
7-1.1.2 图灵机的计算复杂性
对于输入x，定义$t_M(x):=$M在x上的运行步数（时间复杂性），$s_M(x):=$M在x上运行所用到的格子数（空间复杂性）。
我们也可以根据输入长度n来定义时间复杂性：$t_M(n):=$M在长度为n的输入上的运行步数。由于长度相同的输入运行时间可能不同，因此$t_M(n)$有两种取值策略：最坏情况(worst-case)时间复杂度、平均复杂性(average-case)。
7-1.1.3 时空复杂性类
\[TIME(t(n)) = \left\{L\mid L=L(M)，DTM\ M的运行时间复杂度为O(t(n))\right\}\] \[NTIME(t(n)) = \left\{L\mid L=L(M)，NTM\ M的运行时间复杂度为O(t(n))\right\}\] \[SPACE(t(n)) = \left\{L\mid L=L(M)，DTM\ M的运行空间复杂度为O(t(n))\right\}\] \[NSPACE(t(n)) = \left\{L\mid L=L(M)，NTM\ M的运行空间复杂度为O(t(n))\right\}\]包含关系如下：
\[TIME(t(n))\subseteq NTIME(t(n))\] \[TIME(t(n))\subseteq SPACE(t(n))\] \[SPACE(t(n))\subseteq NSPACE(t(n))\] \[NTIME(t(n))\subseteq NSPACE(t(n))\]7-1.1.4 线性加速定理
任意图灵机$M_1$，假设它的复杂度（时间或空间）为$t(n)$，则存在图灵机$M_2$，它的复杂度为$\frac{t(n)}{c}$，且$M_1$与$M_2$等价。
做法：把$M_1$的$c$个格子合成一个格子，并由此形成新的字母表。
7-1.1.5 大O记号
\[f_1(n)=O\big(f_2(n)\big)\]含义：$\exists c>0,\exists N>0$，当$n>N$时，$f_1(n)\leq f_2(n)$。
称$f_2(n)$为$f_1(n)$的渐近上界。
7-1.2 常见的复杂性类
\[P=\bigcup_{k>0}TIME(n^k)\] \[NP=\bigcup_{k>0}NTIME(n^k)\] \[coNP:NP的补类\] \[EXP=\bigcup_{k>0}TIME\big(2^{n^k}\big)\] \[NEXP=\bigcup_{k>0}NTIME\big(2^{n^k}\big)\] \[coNEXP:NEXP的补类\]关于它们，有很多未知的内容：
\[NEXP\stackrel{?}{=}coNEXP\] \[NEXP\stackrel{?}{=}NP\] \[NP\stackrel{?}{=}coNP\] \[NP\cap coNP\stackrel{?}{=}P\] \[P\stackrel{?}{=}NP\]不过有一点倒是可以确定，$P\neq EXP$。
7-1.3 模型间的复杂性关系
定理1 $O(t(n))$的多带DTM可以转换为$O(t^2(n))$的单带DTM。
证明思路：回顾多带DTM转化为单带DTM的方法，我们采用了“分段”的策略。首先，先把单带按照多带的输入配置好，这需要$O(n)$步。这之后，对于多带上的每一步，单带上最多要运行$O(t(n))$步，又知道多带一共要运行$t(n)$步，因此一共需要运行$O(n)+t(n)\cdot O(t(n))=O(t^2(n))$步（可以合理地假定$t(n)>n$，否则连多带图灵机输入都读不完）。
定理2 $O(t(n))$的单带NTM可以转换为$2^{O(t(n))}$的单带DTM。
证明思路：寻找计算分支，对每个分支最多模拟$t(n)$步，一共有最多$b^{t(n)}$个分支，其中b是每个结点的分支数的最大值。因此单带DTM的运行时间是$O(t(n)b^{t(n)})=2^{O(t(n))}$。
7-1.4 P与NP
- P类的封闭性
P类对交、并、补、星号运算封闭。
可以用动态规划的方法解决P对星号运算封闭的问题。
- NP类的一个等价定义
NP类的另一个等价定义：
\[L\in NP\Leftrightarrow L=\left\{x\mid \exists y, \mid y\mid =\mid x\mid ^{O(1)}=poly(\mid x\mid ),\langle x,y\rangle \in C\right\}\]这里的$C\in P$。这个定义的意思是，输入x，它首先是多项式时间可判定的，且它的解y的长度是其多项式函数。
例如，考虑SAT问题，对于布尔公式$\phi$和一组布尔公式的赋值$a$，可以定义C:
\[C=\left\{\langle \phi,a \rangle \mid \phi(a)=1\right\}\in P\]$a$是一组赋值$a_1,a_2,…,a_n$，而$\phi $是一个布尔函数$\phi(x_1,x_2,…,x_n)$，它们的长度的确呈多项式关系，而且对C的判定也可以在多项式时间内解决，因此SAT问题属于NP问题。
注意到，这里$L$的形式定义，除了限定了$C\in P$以及对y的长度做了限制，其它都与$\Sigma_1$的描述形式一致，因此又称NP为$\Sigma_1^P$。