BPP

In complexity theory, BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/4 for all instances. The abbreviation BPP refers to Bounded-error, Probabilistic, Polynomial time.

If a problem in in BPP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/4 of giving the wrong answer. That is true, whether the answer is YES or NO.

It is known that BPP=Co-BPP. It is an open question whether BPP is a subset of NP. It is an open question whether NP is a subset of BPP. If it is, then NP=RP. It is known that RP? is a subset of BPP, and BPP is a subset of PP?. It is not known whether those two are strict subsets.

This class is defined for an ordinary Turing machine plus a source of randomness. The corresponding class for a quantum computer is BQP.

/Talk