NTIME
#計算複雑性理論
#計算複雑性クラス
$ T : \mathbb{N} \to \mathbb{N}, 言語$ L \subseteq 2^*について, $ Lが$ \textbf{NTIME}(T)であるとは、定数$ cが存在して時間$ cT(n)以下で決定する非決定性チューリングマシンが存在することである
$ L \in \textbf{NTIME}(T) \iff \exists e. \exists c.\forall x. [N_{e, cT(|x|)}(x) = 1 \iff x \in L]
関連
DTIME