BPP (complexity)

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances.

BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines.

Informally, a problem is in BPP if there is an algorithm for it that has the following properties: A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that Unlike the complexity class ZPP, the machine M is required to run for polynomial time on all inputs, regardless of the outcome of the random coin flips.

A language L is in BPP if and only if there exists a polynomial p and deterministic Turing machine M, such that In this definition, the string y corresponds to the output of the random coin flips that the probabilistic Turing machine would have made.

For some applications this definition is preferable since it does not mention probabilistic Turing machines.

Modifying the definition to use any constant between 0 and 1/2 (exclusive) in place of 1/3 would not change the resulting set BPP.

The chance that the majority of the runs are wrong drops off exponentially as a consequence of the Chernoff bound.

Adding postselection to BPP, or allowing computation paths to have different lengths, gives the class BPPpath.

Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time.

Las Vegas algorithms with polynomial bound running times are used to define the class ZPP.

Alternatively, ZPP contains probabilistic algorithms that are always correct and have expected polynomial running time.

For a fixed ENP (relativized) complete problem, the oracle will give correct answers with high probability if queried with the problem instance followed by a random string of length kn (n is instance length; k is an appropriate small constant).

The lemma ensures that (for a large enough k), it is possible to do the construction while leaving enough strings for the relativized ENP answers.

The existence of certain strong pseudorandom number generators is conjectured by most experts of the field.

[8] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson showed that unless EXPTIME collapses to MA, BPP is contained in[9] The class i.o.-SUBEXP, which stands for infinitely often SUBEXP, contains problems which have sub-exponential time algorithms for infinitely many input sizes.

Russell Impagliazzo and Avi Wigderson showed that if any problem in E, where has circuit complexity 2Ω(n) then P = BPP.