复杂度类 RP

RP 算法像随机寻找一个可验证见证，其误差只有一侧：否实例绝不会被误接受，是实例则以至少常数概率找到可验证成功。可以把随机位看成候选见证生成器；一旦算法回答“是”，结果具有确定可靠性，而“否”可能只是本轮运气不好。重复运行并取 OR 可指数降低漏报概率，同时保持零假阳性。

若单次在是实例上以至少 $1/2$ 接受，独立运行 $k$ 次，只要一次接受就回答“是”，漏报概率至多 $2^{-k}$。多项式恒等式测试的某些版本具有类似单边结构：检测到不相等是确定证据，而随机点恰巧相等会造成漏判。

因此定义中的常数 $1/2$ 可替换为任意固定正常数，再借重复放大到接近 1。算法使用的随机比特数须多项式有界，且概率针对内部随机性；它还必须对所有否实例在每条随机分支都拒绝，仅“错误概率很小”属于 BPP 型双边误差。交换接受与拒绝得到 coRP：是实例从不误拒，否实例可能误接受，而不是仍叫 RP。

有

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

概率放大公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。 对 RP 采用 OR 规则，和 BPP 的多数投票不同。该类包含 P、包含于 BPP公理库复杂度类 BPPComplexity class BPP具有有界双边误差多项式时间随机算法的语言类。，并与 ZPP公理库复杂性类 ZPPZero-error probabilistic polynomial time · ZPP可由零错误、期望多项式时间随机算法判定的语言类。 通过 $ZPP=RP\cap coRP$ 相连；随机代数算法常以 RP/coRP 语言精确描述其可靠方向。