在复杂度理论内，RP（"随机多项式时间"）是一个有关几率图灵机的复杂度类，并且存在以下特性：
换句话说，这个算法允许在操作的时候进行全然几率的猜测。这个算法会回传YES的状况必然是输入为真的状况；因此如果这个算法说了YES，那我们就知道了这个输入必定为是：不过，这个算法可以在不管正确解答为何的时候回传NO。也就是，如果这个算法回传答案是错的，可能是这个算法犯错了（也就是其实这个输入应该是对的）。
有一些作者叫这一个复杂度类R，不过这个名字更常被使用于定义包含了所有递归语言的复杂度类。
如果输入的答案为"是"且这个算法运作了次，每次跑出来的答案统计上独立于其他答案，那回传起码一次YES的几率则至少有1 − 2−这么多。所以如果这个算法跑了够多的次数，那数学上来说他回传错误解答的几率就会变得非常非常小，甚至小过运算的电脑被宇宙射线影响因此错误的几率。在这个概念上，如果我们有一个够好的乱数来源，大多数的RP算法都是非常具有实做价值的。
这里选用的1/2这个常数，是不需要太严格的一个选择：无论我们将定义里面的1/2换成任何小于1的非零常数，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是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里面的是等同多项式检定，此问题决定给予的多变量整数多项式是否等于一个零多项式。举例来说, · - · - ( + )·( - )是一个零多项式，而· + ·则不是。
另一种有时候比较好使用的RP的定义是能够被非决定型图灵机解决问题的集合。此机器接受答案，当且仅当至少有常数比例条计算路径（此常数与输入长度无关）回传解答为"是"。另一方面NP则只需要一条路径回传答案为是，这件事实使我们针对同一个问题可以建立比较少的路径。因此，此特征显示出RP显然是NP的子集合。
