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