RTIME
#計算複雑性理論
#計算複雑性クラス
#乱択計算
RTIMEは一方向に確率的なアルゴリズム
$ T : \N \to \N
について
$ L \in \mathbf{RTIME}(T)
であるとは
$ T
時間計算可能な
PTM
$ \mathcal{M}
が存在して
$ x \in L \Rightarrow \Pr[\mathcal{M}(x) = 1] \ge \frac{2}{3}
$ x \notin L \Rightarrow \mathcal{M}(x) = 0
を満たす計算複雑性クラスである