https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=NSPACE 2026-07-10T15:48:26Z 在这个wiki上该页的修订历史 MediaWiki 1.43.9 https://arolstar52-zhtest.hf.space/index.php?title=NSPACE&diff=784780&oldid=prev 2026-01-01T13:15:07Z

<p>修正笔误</p> <p><b>新页面</b></p><div>{{Refimprove|time=2025-09-08T18:38:47+00:00}}<br /> 在[[計算複雜度理論]]中，[[複雜度類]]&#039;&#039;&#039;NSPACE(&#039;&#039;f&#039;&#039;(&#039;&#039;n&#039;&#039;))&#039;&#039;&#039;是一個[[決定性問題|可判定问题]]的集合，它是所有不限制时间的[[非确定性图灵机]]在至多&#039;&#039;O&#039;&#039;(&#039;&#039;f&#039;&#039;(&#039;&#039;n&#039;&#039;))空间内可判定的问题组成的复杂度类。<br /> 这是确定性空间类[[DSPACE]]在非确定性计算模型下的推广。<br /> <br /> &#039;&#039;&#039;NSPACE&#039;&#039;&#039;可以用来定义一些重要的复杂度类。这些复杂度类包括：<br /> <br /> * &#039;&#039;&#039;[[正則語言|REG]]&#039;&#039;&#039; = &#039;&#039;&#039;DSPACE&#039;&#039;&#039;(&#039;&#039;O&#039;&#039;(1)) = &#039;&#039;&#039;NSPACE&#039;&#039;&#039;(&#039;&#039;O&#039;&#039;(1))，這裡 &#039;&#039;&#039;REG&#039;&#039;&#039;是[[正則語言]]（regular language）对应的複雜度類（这是因为非确定性无法扩展可识别语言的范围）。<br /> * &#039;&#039;&#039;[[NL (複雜度)|NL]]&#039;&#039;&#039; = &#039;&#039;&#039;NSPACE&#039;&#039;&#039;(&#039;&#039;O&#039;&#039;(log&amp;nbsp;&#039;&#039;n&#039;&#039;))<br /> * &#039;&#039;&#039;[[上下文有關語言|CSL]]&#039;&#039;&#039; = &#039;&#039;&#039;NSPACE&#039;&#039;&#039;(&#039;&#039;O&#039;&#039;(&#039;&#039;n&#039;&#039;))，其中&#039;&#039;&#039;CSL&#039;&#039;&#039;是[[上下文有關語言]]（context-sensitive language）对应的複雜度類。<br /> * &#039;&#039;&#039;[[PSPACE]]&#039;&#039;&#039; = &#039;&#039;&#039;NPSPACE&#039;&#039;&#039; = &lt;math&gt;\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(n^k)&lt;/math&gt;<br /> * &#039;&#039;&#039;[[EXPSPACE]]&#039;&#039;&#039; = &#039;&#039;&#039;NEXPSPACE&#039;&#039;&#039; = &lt;math&gt;\bigcup_{k\in\mathbb{N}} \mbox{NSPACE}(2^{n^k})&lt;/math&gt;<br /> <br /> 由[[薩維奇定理]]可導出最后两个结论。该定理表明，对于任何&#039;&#039;f&#039;&#039;(&#039;&#039;n&#039;&#039;) ≥ log(&#039;&#039;n&#039;&#039;)，都有<br /> <br /> :&#039;&#039;&#039;NSPACE&#039;&#039;&#039;(&#039;&#039;f&#039;&#039;(&#039;&#039;n&#039;&#039;)) ⊆ &#039;&#039;&#039;DSPACE&#039;&#039;&#039;(&#039;&#039;f&#039;&#039;&lt;sup&gt;2&lt;/sup&gt;(&#039;&#039;n&#039;&#039;))。<br /> <br /> 因此，当 &lt;math&gt;f(n)&lt;/math&gt; 为多项式或指数函数时，非确定性空间与确定性空间在相应的复杂度类中等价。<br /> <br /> [[Immerman–Szelepcsényi定理]]則指出對任何{{nowrap|&#039;&#039;s&#039;&#039;(&#039;&#039;n&#039;&#039;) ≥ log &#039;&#039;n&#039;&#039;}}，&#039;&#039;&#039;NSPACE&#039;&#039;&#039;(&#039;&#039;s&#039;&#039;(&#039;&#039;n&#039;&#039;))在補集運算下封閉(closed under complement)。<br /> <br /> &#039;&#039;&#039;NSPACE&#039;&#039;&#039;可以與[[DTIME]]作連接如下：<br /> 對任何[[space constructible function]] &#039;&#039;s&#039;&#039;(&#039;&#039;n&#039;&#039;),<br /> :&lt;math&gt;\mbox{NSPACE}(s(n)) \subseteq \bigcup_{k \geq 1} \mbox{DTIME}(2^{k \cdot s(n)})&lt;/math&gt;<br /> <br /> ==參考資料==<br /> {{ComplexityZoo|NSPACE(&#039;&#039;f&#039;&#039;(&#039;&#039;n&#039;&#039;))|N#nspace}}.<br /> <br /> {{複雜度類}}<br /> <br /> {{DEFAULTSORT:Nspace}}<br /> [[Category:複雜度類]]<br /> [[Category:計算資源]]</div>

imported>KrisTHL181