Vipul: Created page with "{{complexity class}} ==Definition== '''RP''' or '''randomized polynomial time''' is a complexity class that can loosely be described as a class of languages in which membership..."

2011-12-27T20:47:31Z

Created page with "{{complexity class}} ==Definition== '''RP''' or '''randomized polynomial time''' is a complexity class that can loosely be described as a class of languages in which membership..."

New page

{{complexity class}}

==Definition==

'''RP''' or '''randomized polynomial time''' is a complexity class that can loosely be described as a class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, where a ''Yes'' answer for a given string always means that the string is in the language, and, for any string in the language, the probability that a ''No/Maybe'' answer would be returned ''for that string'' is bounded from above by a number strictly less than 1.

There are three aspects to this:

* The algorithm has access to a random oracle, that may provide up to polynomially many pure random bits that the algorithm can use.
* The probability of giving a wrong answer is measured as the probability ''over'' the choices of random bits but ''not'' over the choice of input strings. Rather, for input strings, we are still interested in the worst case probability.

RP - Revision history

Vipul: Created page with "{{complexity class}} ==Definition== '''RP''' or '''randomized polynomial time''' is a complexity class that can loosely be described as a class of languages in which membership..."