https://arolstar52-zhtest.hf.space/index.php?action=history&feed=atom&title=NTIME NTIME - 版本历史 2026-07-15T17:30:34Z 在这个wiki上该页的修订历史 MediaWiki 1.43.9 https://arolstar52-zhtest.hf.space/index.php?title=NTIME&diff=628961&oldid=prev imported>InternetArchiveBot：​补救1个来源，并将0个来源标记为失效。 #IABot (v1.5beta) 2017-08-01T03:34:51Z <p>补救1个来源，并将0个来源标记为失效。 #IABot (v1.5beta)</p> <p><b>新页面</b></p><div>{{專家|time=2015-09-16T09:02:55+00:00}}<br /> {{擴充|time=2015-09-16T09:02:40+00:00}}<br /> 在[[計算複雜性理論]]裡面，[[複雜度類]]&#039;&#039;&#039;NTIME(&#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 /> [[NP (複雜度)|NP]]這個有名的複雜度類，可以用NTIME來定義如下：<br /> :&lt;math&gt;\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)&lt;/math&gt;<br /> <br /> 相同的，[[NEXPTIME]]這個複雜度類是由NTIME定義出來的，非決定型的[[時間譜系理論]]說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。<br /> <br /> ==參考資料==<br /> *（英文）[https://web.archive.org/web/20100727020050/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AN#ntime Complexity Zoo: NTIME]<br /> <br /> {{复杂度类}}<br /> {{计算理论小作品}}<br /> [[Category:複雜度類]]<br /> [[Category:計算資源]]</div> imported>InternetArchiveBot