NTIME：修订间差异

删除的内容添加的内容

行内

2017年8月1日 (二) 03:34的最新版本

在計算複雜性理論裡面，複雜度類NTIME(f(n))是一種可以用非確定型圖靈機使用O(f(n))的時間和無限制的空間所能解決的所有決定性問題的集合。 NP這個有名的複雜度類，可以用NTIME來定義如下：

{\mbox{NP}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(n^{k})

相同的，NEXPTIME這個複雜度類是由NTIME定義出來的，非決定型的時間譜系理論說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。

參考資料

（英文）Complexity Zoo: NTIME

P ≟ NP

这是一篇关于计算理论的小作品。您可以通过编辑或修订扩充其内容。

@@ 第1行： / 第1行： @@
+{{專家|time=2015-09-16T09:02:55+00:00}}
-在[[計算複雜性理論]]裡面, [[複雜度類]] '''NTIME(''f''(''n''))'''是一種可以用[[非確定型圖靈機]]使用''O''(''f''(''n''))的時間和無限制的空間所能解決的所有[[決定性問題]]的集合。
+{{擴充|time=2015-09-16T09:02:40+00:00}}
+在[[計算複雜性理論]]裡面，[[複雜度類]]'''NTIME(''f''(''n''))'''是一種可以用[[非確定型圖靈機]]使用''O''(''f''(''n''))的時間和無限制的空間所能解決的所有[[決定性問題]]的集合。
 [[NP (複雜度)|NP]]這個有名的複雜度類，可以用NTIME來定義如下：
 :<math>\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)</math>
-相同的，[[NEXPTIME]]這個複雜度類是由NTIME定義出來的，非決定型的[[時間層級定理]]說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。
+相同的，[[NEXPTIME]]這個複雜度類是由NTIME定義出來的，非決定型的[[時間譜系理論]]說明了非決定型的機器在使用更多時間的前提下可以解決更多的問題。
 ==參考資料==
+*（英文）[https://web.archive.org/web/20100727020050/http://qwiki.stanford.edu/wiki/Complexity_Zoo%3AN#ntime Complexity Zoo: NTIME]
+{{复杂度类}}
-<!--{{ComplexityZoo|NTIME(''f''(''n''))|N#ntime}}.-->
+{{计算理论小作品}}
-{{複雜度類}}
-{{DEFAULTSORT:Ntime}}
-{{comp-sci-theory-stub}}
-<!--[[Category:Computational resources]]-->
 [[Category:複雜度類]]
+[[Category:計算資源]]
-[[de:NTIME]]
-[[en:NTIME]]
-[[es:NTIME]]
-[[nl:NTIME]]
-[[ja:NTIME]]