RP (复杂度)
此条目没有列出任何参考或来源. (2008年7月1日)
在复杂度理论内,RP("随机多项式时间")是一个有关机率图灵机的复杂度类,并且存在以下特性:
RP演算法(单次操作)
产生的答案
解答 是 否
是 ≥ 1/2 ≤ 1/2
否 0 1
RP演算法(n次操作)
是 ≥ 1 − 2−n ≤ 2−n
co-RP演算法(单次操作)
产生的解答
是 1 0
否 ≤ 1/2 ≥ 1/2
此演算法总是跑输入大小的多项式长度这么多的时间
如果输入的答案为非,此演算法会回传NO
如果输入的答案为是,则回传YES的机率至少1/2(其余的机率则是回传NO).
换句话说,这个演算法允许在操作的时候进行全然机率的猜测.这