形式陈述

语言 $L$ 属于 $\mathrm{RP}$，若存在概率多项式时间算法 $A$，使对每个输入 $x$：

$$x\notin L⟹\text{Pr}[A(x)=1]=0,$$$$x\in L⟹\text{Pr}[A(x)=1]\ge \frac{1}{2}.$$

错误是单边的：算法接受时结论必真，但对“是”实例可能误拒绝。独立重复 $k$ 次并在任一次接受时接受，可把误拒概率降到 $2^{-k}$，仍保持零假阳性。

直觉

RP 算法像随机寻找一个可验证见证：找到时可以确信答案为“是”，没找到则可能只是运气不好。重复搜索能快速降低漏报概率。

例子与边界

常数 $1/2$ 可替换为任意固定正常数，借重复放大到接近 1。若把输出反转得到 coRP：是实例从不误拒，否实例可能误接受。RP 中的随机比特数须多项式有界，且概率针对算法内部随机性。

推论与应用

有

$$\mathrm{P}\subseteq \mathrm{RP}\subseteq \mathrm{NP}\cap \mathrm{BPP},$$

其中 RP 到 NP 可固定一条导致接受的随机串作为证书。RP 用于随机代数算法与某些身份测试的单边误差版本；具体问题是否在 RP 取决于已知算法。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 7。
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995，Ch. 1。