NTIME

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

<math>\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)</math>

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

參考資料

• （英文）Complexity Zoo: NTIME