BPP (complexity)

bpp, conventionally written BPP, is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with the probability of an incorrect answer bounded away from one half. The abbreviation denotes bounded-error probabilistic polynomial time. BPP is a central model for efficient randomized computation with two-sided error, meaning that either an accepting or a rejecting computation can be incorrect.

The numerical error bound used in the definition is conventional rather than intrinsic. Any fixed bound strictly below one half defines the same class because independent repetitions can reduce the error probability while preserving polynomial running time. This stability distinguishes BPP from models in which an algorithm has only a negligibly greater probability of success than random guessing.

Formal definition

A language (L) belongs to BPP if there exists a probabilistic Turing machine (M) and a polynomial (p) such that (M) halts within (p(|x|)) steps on every input (x), and

[ x\in L \quad\Longrightarrow\quad \Pr[M(x)\text{ accepts}]\geq \frac{2}{3}, ]

while

[ x\notin L \quad\Longrightarrow\quad \Pr[M(x)\text{ accepts}]\leq \frac{1}{3}. ]

The probabilities are taken over the machine's internal random choices. A standard formulation gives the machine access to independent unbiased random bits, although equivalent definitions use a polynomially bounded random string supplied as an additional input.

Under the random-string formulation, there is a deterministic polynomial-time machine (D) and a polynomial (q) for which

[ \Pr_{r\in{0,1}^{q(|x|)}}[D(x,r)=L(x)]\geq \frac{2}{3}. ]

Thus, a BPP computation can also be regarded as a polynomial-size distribution over deterministic computations. The bounded running time applies to every random string rather than merely to the expected running time.

Error reduction

The constant (1/3) can be replaced by any fixed (\varepsilon<1/2) without changing BPP. If a machine has success probability at least (1/2+\delta), where (\delta) is a positive constant, it can be run independently several times and its majority output can be returned. A Chernoff bound shows that the resulting error decreases exponentially in the number of repetitions.

For an input of length (n), polynomially many repetitions can therefore reduce the error to (2^{-p(n)}) for any chosen polynomial (p). The running time remains polynomial because the original computation and the number of repetitions are both polynomially bounded.

Amplification also establishes closure under complement. Reversing the accepting and rejecting outcomes of a BPP machine decides the complementary language with the same error probability. Amplification followed by standard Boolean composition establishes closure under finite union and finite intersection.

Historical development

John Gill introduced probabilistic polynomial-time classes in 1977 through a systematic study of probabilistic Turing machines. His formulation separated bounded-error computation from the unbounded-error model represented by PP and from one-sided-error computation represented by RP.

In 1982, You Watanabe established the constant-gap invariance of the definition and gave a fair-coin normal form for machines whose transition probabilities were polynomial-time samplable rationals. The normal form uses approximation followed by amplification, so replacing the original transitions with unbiased random-bit computations preserves a bounded separation between acceptance and rejection probabilities. This treatment contributed to the machine-independent formulation used in subsequent work on randomized complexity classes.

Relationship with deterministic and randomized classes

Every deterministic polynomial-time computation is a BPP computation that ignores its random bits. Consequently,

[ \mathrm{P}\subseteq\mathrm{BPP}. ]

The zero-error class ZPP is contained in BPP because a zero-error expected-polynomial-time computation can be truncated and converted into a bounded-error worst-case polynomial-time computation. The one-sided classes RP and co-RP are also contained in BPP after their error probabilities are reduced.

Every BPP language belongs to PP because a BPP machine already accepts yes-instances with probability greater than one half and accepts no-instances with probability less than one half. PP permits the gap from one half to be exponentially small, whereas BPP requires an inverse-constant gap before amplification. Since PP is contained in PSPACE, BPP is contained in PSPACE as well.

These relationships can be summarized by

[ \mathrm{P}\subseteq\mathrm{ZPP}\subseteq\mathrm{RP}\subseteq\mathrm{BPP} \subseteq\mathrm{PP}\subseteq\mathrm{PSPACE}, ]

with co-RP separately contained in BPP. None of the principal containments between P, RP, ZPP, and BPP is known to be strict in the unrelativized setting.

Circuit and hierarchy bounds

Leonard Adleman proved that every BPP language has polynomial-size Boolean circuits, giving the nonuniform containment

[ \mathrm{BPP}\subseteq\mathrm{P/poly}. ]

The proof amplifies a BPP machine until its error on each input is smaller than the reciprocal of the number of inputs of a fixed length. A union bound then shows that, for every input length, at least one random string makes the machine correct on all inputs of that length. Fixing such a string yields a polynomial-size circuit family, although the argument does not provide a uniform polynomial-time method for finding the strings.

A further structural result places BPP in the second level of the polynomial hierarchy:

[ \mathrm{BPP}\subseteq\Sigma_2^{\mathrm P}\cap\Pi_2^{\mathrm P}. ]

Michael Sipser and Péter Gács developed the initial form of this simulation, and Clemens Lautemann supplied the standard geometric covering proof. The argument represents accepting random strings as a dense subset of a Boolean cube and expresses the existence of a small collection of translations that covers the cube. The resulting statement has an existential quantifier followed by a universal quantifier, which yields membership in (\Sigma_2^{\mathrm P}); closure under complement supplies the corresponding (\Pi_2^{\mathrm P}) containment.

Derandomization

Whether

[ \mathrm{P}=\mathrm{BPP} ]

remains unresolved. The equality would mean that randomness provides no asymptotic increase in polynomial-time decision power under the bounded-error criterion, although randomized algorithms could still differ from deterministic ones in their concrete complexity.

Derandomization studies replace truly random bits with outputs of pseudorandom generators that are indistinguishable from randomness by the computation being simulated. If a generator stretches a short seed into enough pseudorandom bits, all seeds can be enumerated in deterministic polynomial time and the majority result can reproduce the randomized computation.

Noam Nisan and Avi Wigderson connected this construction to circuit lower bounds through the hardness-versus-randomness paradigm. Russell Impagliazzo and Wigderson subsequently proved that sufficiently strong worst-case hardness for functions in E implies (\mathrm{P}=\mathrm{BPP}). These results formalize the principle that computationally hard functions can generate strings that appear random to bounded computations.

The converse direction also has structural content. Effective general-purpose derandomization yields explicit objects that resist restricted computational models, so derandomization and lower-bound questions are linked rather than independent.

Relativization

There are oracles relative to which P and BPP are unequal, as well as oracles relative to which they coincide. Therefore, a proof of the unrelativized equality cannot follow solely from techniques that remain valid under every oracle extension.

Oracle separations do not determine the ordinary relationship between P and BPP. They instead identify a limitation of relativizing proof methods, paralleling the role of oracle results in the study of P versus NP.

Promise-problem formulation

Randomized algorithms are frequently expressed as promise problems, in which inputs are restricted to a specified yes-set or no-set. The corresponding class is commonly denoted Promise-BPP. Its completeness theory is more natural than that of BPP because the acceptance-probability gap itself defines a promise: valid instances must have acceptance probability at least (2/3) or at most (1/3), while intermediate cases are excluded.

The canonical promise problem asks whether a given probabilistic polynomial-time computation has high or low acceptance probability. This formulation connects BPP to approximate counting, interactive proof systems, and probabilistic verification without asserting behavior on computations whose acceptance probabilities lie inside the forbidden interval.