空间阶层定理

阐述

称一个函数 $f:N\to N$ 且 $f(n)\ge O(\log n)$ 是空间可构造的，如果能以 $O(f(n))$ 空间将纸带上的 $1^n$ 转换为 $f(n)$ 的二进制表示。特别地，对于次线性的函数来说 $1^n$ 是只读的。

对于任何空间可构造函数 $f$ 来说，存在一个语言 $A$ 可以在 $O(f(n))$ 时间内判别，但不能在 $o(f(n))$ 时间内判别。

推论：

如果 $f_1(n)=o(f_2(n))$ 且 $f_2$ 可构造，那么 $\operatorname{SPACE}\left(f_{1}(n)\right) \subsetneq \operatorname{SPACE}\left(f_{2}(n)\right)$
对于任何实数 $0\le\varepsilon_1<\varepsilon_2$ ， $\operatorname{SPACE}\left(n^{\epsilon_{1}}\right) \subsetneq \operatorname{SPACE}\left(n^{\epsilon_{2}}\right)$
$\mathrm{NL}\subsetneq\mathrm{PSPACE}$
$\mathrm{PSPACE}\subsetneq\mathrm{EXPSPACE}$

定义一个语言是指数空间完全的，如果它属于指数空间且所有指数空间中的语言都可以归约为它。

E Q_{\mathrm{REX} \uparrow}=\{\langle Q, R\rangle \mid Q \text { and } R \text{ are equivalent RE with exponentiation}\}

这个语言是指数空间完全的，因此肯定不属于 P。