空间阶层定理

空间阶层定理需要使用空间可构函数。若一个函数${\displaystyle f:\mathbb {N} \longrightarrow \mathbb {N} }$ 满足如下条件：${\displaystyle f(n)\geq \log ~n}$ ，且存在一图灵机可以在输入为${\displaystyle 1^{n}}$ 时、使用${\displaystyle O(f(n))}$ 存储空间的条件下计算该函数${\displaystyle f}$ ，则称该函数为空间可构造函数。其中${\displaystyle 1^{n}}$ 表示一个内容为n个连续的1的字符串。许多常见函数都是空间可构造的，例如多项式函数、指数函数、对数函数等。

确定型和不确定型的空间阶层定理的内容是：对于所有空间可构造函数${\displaystyle f(n)}$ ，

${\displaystyle {\mathsf {DSPACE}}\left(o(f(n))\right)\subsetneq {\mathsf {DSPACE}}(f(n))}$ ，且

${\displaystyle {\mathsf {NSPACE}}\left(o(f(n))\right)\subsetneq {\mathsf {NSPACE}}(f(n))}$ ，

其中DSPACE（英语：DSPACE）和NSPACE分别对应确定型和不确定型空间复杂度类，而${\displaystyle o(\cdot )}$ 是指小o符号。

空间阶层定理的另一种表述方式是，对于任意的空间可构造函数${\displaystyle f:\mathbb {N} \longrightarrow \mathbb {N} }$ ，都存在一个语言L，它可以在${\displaystyle O(f(n))}$ 存储空间上被决定，但在${\displaystyle o(f(n))}$ 存储空间上则不行。

• 计算复杂性理论
• 空间复杂度
• 时间阶层定理