在計算複雜度理論中，複雜度類*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(f2(n))。
因此，当 f(n) 为多项式或指数函数时，非确定性空间与确定性空间在相应的复杂度类中等价。
Immerman–Szelepcsényi定理則指出對任何，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)})
參考資料
.
评论 (0)