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))。

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)).

易解复杂度类

对数空间相关	DLOGTIME AC⁰（英语：AC0） ACC⁰（英语：ACC0） TC⁰（英语：TC0） L · FL · SL · NL NC SC PolyL

多项式空间相关	P（P-完全） FP（英语：FP (complexity)） ZPP RP BPP BQP（QMA（英语：QMA） PostBQP（英语：PostBQP） EQP（英语：EQP））