空间阶层定理

在计算复杂性理论中，空间阶层定理（英語：Space hierarchy theorem）是一组结论，它们表明在一定条件下，确定型和不确定型图灵机在可用的（渐进）存储空间越多时，能用于解答的问题也就越多。^[1]例如，一个确定型图灵机在使用${\displaystyle n\log {n}}$存储空间时可以求解比使用${\displaystyle n}$存储空间时更多的决定性问题。在时间复杂度分析中的类似结论是时间阶层定理。

阶层定理的提出建立在这样的直觉之上：能允许使用的时间或空间越多，就应该能求解更多函数（或决定更多语言）。阶层定理可以用来展现时间或空间复杂度类可以形成一个金字塔型结构：约束越紧，则能决定的语言就越少。

定义

空间阶层定理需要使用空間可構函數。若一个函数${\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))}$ 存储空间上则不行。

参见

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

参考资料

1. Sipser, Michael. Halting Space-Bounded Computations. Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 1978.