NTIME

NTIME(f(n)) とは、計算複雑性理論における複雑性クラスの表現法であり、非決定性チューリング機械を使って O(f(n)) の時間と無制限の空間（領域）を使って解くことが出来る決定問題の集合である。

よく知られている複雑性クラス NP は NTIME を使って次のように表現できる。

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

同様に、NEXPTIME クラスも NTIME を使って定義される。非決定性(時間階層定理)によれば、漸近的により多くの時間をかければ、非決定性機械でより多くの問題を解くことができるとされている。