查看“︁空间阶层定理”︁的源代码

{{NoteTA
|G1=IT
|G2=Math
}}
在[[计算复杂性理论]]中，'''空间阶层定理'''（{{lang-en|'''Space hierarchy theorem'''}}）是一组结论，它们表明在一定条件下，[[确定型图灵机|确定型]]和[[不确定型图灵机]]在可用的（[[渐进分析|渐进]]）存储空间越多时，能用于解答的问题也就越多。<ref>{{cite conference | first = Michael | last = Sipser | title = Halting Space-Bounded Computations | book-title = Proceedings of the 19th Annual Symposium on Foundations of Computer Science | date = 1978}}</ref>例如，一个[[确定型图灵机]]在使用<math>n\log{n}</math>存储空间时可以求解比使用<math>n</math>存储空间时更多的[[决定性问题]]。在时间复杂度分析中的类似结论是[[时间阶层定理]]。

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

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

确定型和不确定型的空间阶层定理的内容是：对于所有空间可构造函数<math>f(n)</math>，

:<math>\mathsf{DSPACE}\left(o(f(n))\right) \subsetneq \mathsf{DSPACE}(f(n))</math>，且
:<math>\mathsf{NSPACE}\left(o(f(n))\right) \subsetneq \mathsf{NSPACE}(f(n))</math>，

其中{{tsl|en|DSPACE}}和[[NSPACE]]分别对应确定型和不确定型空间复杂度类，而<math>o(\cdot)</math>是指{{tsl|en|small o|小o符号}}。

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

==参见==
* [[计算复杂性理论]]
* [[空间复杂度]]
* [[时间阶层定理]]

==参考资料==
{{reflist}}

[[Category:算法分析]]
[[Category:計算複雜性理論]]