RP (复杂度)
在复杂度理论内，RP（"随机多项式时间"）是一个有关几率图灵机的复杂度类[1]，并且存在以下特性：
| RP算法（单次操作） | ||
|---|---|---|
| 产生的答案 | ||
| 正确 解答 |
是 | 否 |
| 是 | ≥ 1/2 | ≤ 1/2 |
| 否 | 0 | 1 |
| RP算法（n次操作） | ||
| 产生的答案 | ||
| 正确 解答 |
是 | 否 |
| 是 | ≥ 1 − 2−n | ≤ 2−n |
| 否 | 0 | 1 |
| co-RP算法（单次操作） | ||
| 产生的解答 | ||
| 正确 解答 |
是 | 否 |
| 是 | 1 | 0 |
| 否 | ≤ 1/2 | ≥ 1/2 |
- 此算法的运行时间不超过一个以输入长度为自变量的多项式函数
- 如果输入的答案为非，此算法会回传NO
- 如果输入的答案为是，则回传YES的几率至少1/2（其余的几率则是回传NO）。
换句话说，这个算法允许在操作的时候进行全然几率的猜测。这个算法会回传YES的状况必然是输入为真的状况；因此如果这个算法说了YES，那我们就知道了这个输入必定为是：不过，这个算法可以在不管正确解答为何的时候回传NO。也就是，如果这个算法回传答案是错的，可能是这个算法犯错了（也就是其实这个输入应该是对的）。
有一些作者叫这一个复杂度类R，不过这个名字更常被使用于定义包含了所有递归语言的复杂度类。
如果输入的答案为"是"且这个算法运作了n次，每次跑出来的答案统计上独立于其他答案，那回传起码一次YES的几率则至少有1 − 2−n这么多。所以如果这个算法跑了够多的次数，那数学上来说他回传错误解答的几率就会变得非常非常小，甚至小过运算的电脑被宇宙射线影响因此错误的几率。在这个概念上，如果我们有一个够好的乱数来源，大多数的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和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的子集合。
相关参阅[编辑]
参考文献[编辑]
- ^ David, Matei; Pitassi, Toniann. Separating NOF communication complexity classes RP and NP. arXiv:0802.3860 [cs]. 2008-02-26 [2023-02-09]. doi:10.48550/arXiv.0802.3860. （原始内容存档于2023-02-09）.
| ||||||||||||||||||||||||||||||||||||
