RP (複雜度)

相关复杂度类

RP的定义告诉我们，如果RP算法说答案是YES，则答案一定为"是"：如果说是NO，则"通常"答案会是"非"。复杂度类co-RP的定义方式类似，不过是说答案是NO的时候，则答案一定是非，说答案是YES的时候答案则"通常"为是。换句话说，RP算法接受了所有的YES状态，而接受或者拒绝了一部分的NO状态。BPP这个复杂度类形容的算法则是在YES状态跟NO状态都有可能犯错的算法，因此它同时包含了RP和co-RP。
RP与co-RP的交集则叫做ZPP。
如同RP有时候被叫做R，有一些作者使用co-R而非co-RP。

与P和NP的关联

P是RP的子集，而RP是NP的子集。 相同的，P也是co-RP的子集，而co-RP则是co-NP的子集。我们尚未知道这一些是否是严格子集（也就是说，这一些集合是否相等或不相等）。然而，一般我们相信P = BPP这个推测是真实的，这样一来的话RP，co-RP，P就全部都是相等的了。如果我们又假设P ≠ NP的话，这就代表说RP严格包含于NP（也就是RP ≠ NP）。我们还不知道是否RP = co-RP，抑或是否RP是NP和co-NP的交集的子集合，不过这些都可以由P = BPP这件事情推论出来。
一个比较自然的例子确定此问题在co-RP里面但是尚不知道是否在P里面的是等同多项式检定，此问题决定给予的多变量整数多项式是否等于一个零多项式。举例来说, x·x - y·y - (x + y)·(x - y)是一个零多项式，而 x·x + y·y则不是。
另一种有时候比较好使用的RP的定义是能够被非决定型图灵机解决问题的集合。此机器接受答案，当且仅当至少有常数比例条计算路径（此常数与输入长度无关）回传解答为"是"。另一方面NP则只需要一条路径回传答案为是，这件事实使我们针对同一个问题可以建立比较少的路径。因此，此特征显示出RP显然是NP的子集合。