# 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

**B**ounded-error,

**P**robabilistic,

**P**olynomial time.

If a problem is 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.

The choice of 1/4 in the definition is arbitrary. It can be any constant between 0 and 1/2 (exclusive) and the set **BPP** will be unchanged. The idea is that there is a small probability of error, but if the algorithm is run many times, the chance that the majority of the runs are wrong is exponentially small.

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.

The existence of certain strong Pseudorandom number generators imply that **P**=**RP**=**BPP**. This is now a widely believed hypothesis.

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