跳转到内容

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