RP

Summary

RP, for randomized polynomial time, is the complexity class of decision problems solved by a polynomial-time probabilistic Turing machine with one-sided error. On a "no" instance the machine always rejects, and on a "yes" instance it accepts with probability at least $1/2$. So an accepting run is a proof that the answer is "yes". It satisfies $\mathrm{P} \subseteq \mathrm{RP} \subseteq \mathrm{NP}$ and $\mathrm{RP} \subseteq$ BPP.