查看“︁NSPACE”︁的源代码

在[[計算複雜度理論]]內，'''NSPACE(''f''(''n''))'''這個[[複雜度類]]是一個[[決定性問題]]的集合，裡面的問題可以以[[非確定型圖靈機]]使用''O''(''f''(''n''))這麼多空間，不限制時間來解決。或者，換句話說，這是[[DSPACE]]的非確定型版本。

有一些重要的複雜度類可以使用'''NSPACE'''來定義。這些複雜度類包括了：

* '''[[正則語言|REG]]''' = '''DSPACE'''(''O''(1)) = '''NSPACE'''(''O''(1))，這裡 '''REG'''是[[正則語言]](regular language)的複雜度類(非確定的特性在常數空間之內並沒有增加計算的能力)。
* '''[[NL (複雜度)|NL]]''' = '''NSPACE'''(''O''(log&nbsp;''n''))
* '''[[上下文有關語言|CSL]]''' = '''NSPACE'''(''O''(''n''))，這裡'''CSL'''是[[上下文有關語言]](context-sensitive language)的複雜度類。
* '''[[PSPACE]]''' = '''NPSPACE''' = <math>\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)</math>
* '''[[EXPSPACE]]''' = '''NEXPSPACE''' = <math>\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})</math>

最後兩個結論是從[[薩維奇定理]]導出，這定理指出對任何''f''(''n'') ≥ log(''n'')，

:'''NSPACE'''(''f''(''n'')) ⊆ '''DSPACE'''(''f''<sup>2</sup>(''n''))。

[[Immerman–Szelepcsényi定理]]則指出對任何{{nowrap|''s''(''n'') ≥ log ''n''}}，'''NSPACE'''(''s''(''n''))在補集運算下封閉(closed under complement)。

'''NSPACE'''可以與[[DTIME]]作連接如下：
對任何[[space constructible function]] ''s''(''n''),
:<math>\mbox{NSPACE}(s(n)) \subseteq \bigcup_{k \geq 1} \mbox{DTIME}(2^{k \cdot s(n)})</math>

==參考資料==
{{ComplexityZoo|NSPACE(''f''(''n''))|N#nspace}}.

{{複雜度類}}

{{DEFAULTSORT:Nspace}}
[[Category:複雜度類]]
[[Category:計算資源]]