跳转到内容

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 nNSPACE(s(n))在补集运算下封闭(closed under complement)。

NSPACE可以与DTIME作连接如下: 对任何space constructible function s(n),

参考资料

Complexity Zoo: NSPACE(f(n)).