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