空間階層定理

在計算複雜性理論中，空間階層定理（英語：Space hierarchy theorem）是一組結論，它們表明在一定條件下，確定型和不確定型圖靈機在可用的（漸進）存儲空間越多時，能用於解答的問題也就越多。例如，一個確定型圖靈機在使用$n\log {n}$存儲空間時可以求解比使用$n$存儲空間時更多的決定性問題。在時間複雜度分析中的類似結論是時間階層定理。

階層定理的提出建立在這樣的直覺之上：能允許使用的時間或空間越多，就應該能求解更多函數（或決定更多語言）。階層定理可以用來展現時間或空間複雜度類可以形成一個金字塔型結構：約束越緊，則能決定的語言就越少。

定義

空間階層定理需要使用空間可構函數。若一個函數$f:\mathbb {N} \longrightarrow \mathbb {N}$滿足如下條件：$f(n)\geq \log ~n$，且存在一圖靈機可以在輸入為$1^{n}$時、使用$O(f(n))$存儲空間的條件下計算該函數$f$，則稱該函數為空間可構造函數。其中$1^{n}$表示一個內容為n個連續的1的字符串。許多常見函數都是空間可構造的，例如多項式函數、指數函數、對數函數等。

確定型和不確定型的空間階層定理的內容是：對於所有空間可構造函數$f(n)$，

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

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

其中DSPACE和NSPACE分別對應確定型和不確定型空間複雜度類，而$o(\cdot )$是指小o符號。

空間階層定理的另一種表述方式是，對於任意的空間可構造函數$f:\mathbb {N} \longrightarrow \mathbb {N}$，都存在一個語言L，它可以在$O(f(n))$存儲空間上被決定，但在$o(f(n))$存儲空間上則不行。

參見

• 計算複雜性理論
• 空間複雜度
• 時間階層定理