[计算理论基础] 层次定理

空间层次定理

空间可构造函数：满足 $f(n)\geq logn$ ，且 $f(n)$ 在 $O(f(n))$ 空间内可计算，输入 $1^n$ ，输出二进制 $f(n)$ .即，存在 TM 以 $f(n)$ 作为空间复杂性。

线性加速定理： $TIME(cf(n))=TIME(f(n))$ , $SPACE(cf(n))=SPACE(f(n))$

带空间限制的通用机： $U(<W,w>)=M(w)$ ，TM U 在 $(f(n))$ 空间内运行。

填塞引理：识别同一个语言的 TM 有无穷多个，用 $<M>10^*$ 表示 $<M>$ 的填塞。

空间层次定理：对于 f，存在语言 A，在 $O(f)$ 空间可判定，但不能在 $o(f)$ 空间内判定。

推论10.4：设 $f_2(n)$ 是空间可构造的，并且 $f_1(n)=o(f_2(n))$ ，则 $SPACE(f_1(n))\subset SPACE(f_2(n))$

推论10.6： $NL\subset PSPACE$

推论10.7： $PSPACE \subset EXPSPACE$

时间可构造函数：t 满足 $t(n)\geq nlogn$ ，并且 $t(n)$ 在 $O(t(n))$ 时间内可计算，输入 $1^n$ ，输出二进制 $t(n)$ .即，存在 TM 以 $t(n)$ 作为时间复杂性。

带时间限制的通用机： $U(<W,w>)=M(w)$ ，TM U 在 $(t(n))$ 时间内运行。

时间层次定理：对于 t，存在语言 A，在 $O(t)$ 时间可判定，但不能在 $o(t/logt)$ 时间内判定。

推论10.11：设 $t_2(n)$ 是时间可构造的，并且 $t_1(n)=o(t_2(n)/logt_2(n))$ ，则 $TIME(t_1(n))\subset TIME(t_2(n))$

推论10.13： $P\subset EXP$