NTIME - 维基百科，自由的百科全书

此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2015年9月16日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。

此條目需要擴充。 (2015年9月16日) 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。

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

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

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

• （英文）Complexity Zoo: NTIME