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 =
- EXPSPACE = NEXPSPACE =
最后两个结论是从萨维奇定理导出,这定理指出对任何f(n) ≥ log(n),
- NSPACE(f(n)) ⊆ DSPACE(f2(n))。
Immerman–Szelepcsényi定理则指出对任何s(n) ≥ log n,NSPACE(s(n))在补集运算下封闭(closed under complement)。
NSPACE可以与DTIME作连接如下: 对任何space constructible function s(n),
参考资料
Complexity Zoo: NSPACE(f(n)).