RP (complexity)
id:
rp-complexity-257-18671573
title:
RP (complexity)
text:
In computational complexity theory, randomized polynomial time (RP) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always runs in polynomial time in the input size
If the correct answer is NO, it always returns NO
If the correct answer is YES, then it returns YES with probability at least 1/2. In other words, the algorithm is allowed to flip a truly random coin while it is running. The only case in which the algorithm can return YES
brand slug:
wiki
category slug:
encyclopedia
description:
Randomized polynomial time class of computational complexity theory
original url:
https://en.wikipedia.org/wiki/RP_(complexity)
date created:
date modified:
2023-07-15T01:20:32Z
main entity:
{"identifier":"Q1190846","url":"https://www.wikidata.org/entity/Q1190846"}
image:
fields total:
13
integrity:
14