NSPACE

在計算複雜度理論中，複雜度類NSPACE(f(n))是一個可判定問題的集合，它是所有不限制時間的非確定性圖靈機在至多O(f(n))空間內可判定的問題組成的複雜度類。 這是確定性空間類DSPACE在非確定性計算模型下的推廣。

NSPACE可以用來定義一些重要的複雜度類。這些複雜度類包括：

• REG = DSPACE(O(1)) = NSPACE(O(1))，這裡 REG是正則語言（regular language）對應的複雜度類（這是因為非確定性無法擴展可識別語言的範圍）。
• NL = NSPACE(O(log n))
• CSL = NSPACE(O(n))，其中CSL是上下文有關語言（context-sensitive language）對應的複雜度類。
• PSPACE = NPSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})$
• EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})$

由薩維奇定理可導出最後兩個結論。該定理表明，對於任何f(n) ≥ log(n)，都有

NSPACE(f(n)) ⊆ DSPACE(f²(n))。

因此，當 $f(n)$ 為多項式或指數函數時，非確定性空間與確定性空間在相應的複雜度類中等價。

Immerman–Szelepcsényi定理則指出對任何s(n) ≥ log n，NSPACE(s(n))在補集運算下封閉(closed under complement)。

NSPACE可以與DTIME作連接如下： 對任何space constructible function s(n),

${\mbox{NSPACE}}(s(n))\subseteq \bigcup _{k\geq 1}{\mbox{DTIME}}(2^{k\cdot s(n)})$

參考資料

Complexity Zoo: NSPACE(f(n)).