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 = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(n^{k})}$
• EXPSPACE = NEXPSPACE = ${\displaystyle \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),

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

参考资料

Complexity Zoo: NSPACE(f(n)).