RP

This article defines a decision complexity class, i.e., a complexity class for decision problems. This means that given any language, the language is either a member of the decision complexity class or it is not a member of the decision complexity class.| View a list of complexity classes

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.