coRP - 国立公園

coRP

#計算複雑性理論

#計算複雑性クラス

定義

$ \mathbf{coRP} := \overline{\mathbf{RP}}

または

$ L \in \mathbf{RP}であるとは多項式時間計算可能なPTM$ \mathcal{M}が存在して

$ x \in L \Rightarrow \mathcal{M}(x) = 1

$ x \notin L \Rightarrow \Pr[\mathcal{M}(x) = 0] \ge \frac{2}{3}

参考