BPP (complexity)
BPP (complexity)
Main page
B

BPP (complexity)

logo
Community Hub0 subscribers
Read side by side
BPP (complexity)
View on Wikipedia
from Wikipedia

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. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic algorithm is a special case of a probabilistic algorithm.

BPP algorithm (1 run)
Answer
produced
Correct
answer
 Yes No
Yes ≥ 2/3 ≤ 1/3
No ≤ 1/3 ≥ 2/3
BPP algorithm (k runs)
Answer
produced
Correct
answer
 Yes No
Yes > 1 − 2−ck < 2−ck
No < 2−ck > 1 − 2−ck
for some constant c > 0

Informally, a problem is in BPP if there is an algorithm for it that has the following properties:

  • It 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/3 of giving the wrong answer, whether the answer is YES or NO.

Definition

[edit]

A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that

  • M runs for polynomial time on all inputs
  • For all x in L, M outputs 1 with probability greater than or equal to 2/3
  • For all x not in L, M outputs 1 with probability less than or equal to 1/3

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.

Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic Turing machine M, such that

  • M runs for polynomial time on all inputs
  • For all x in L, the fraction of strings y of length p(|x|) which satisfy ⁠⁠ is greater than or equal to 2/3
  • For all x not in L, the fraction of strings y of length p(|x|) which satisfy ⁠⁠ is less than or equal to 1/3

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.

In practice, an error probability of 1/3 might not be acceptable; however, the choice of 1/3 in the definition is arbitrary. 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. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1/2100, this would result in the same class of problems. The error probability does not even have to be constant: the same class of problems is defined by allowing error as high as 1/2 − n−c on the one hand, or requiring error as small as 2−nc on the other hand, where c is any positive constant, and n is the length of input. This flexibility in the choice of error probability is based on the idea of running an error-prone algorithm many times, and using the majority result of the runs to obtain a more accurate algorithm. The chance that the majority of the runs are wrong drops off exponentially as a consequence of the Chernoff bound.[1]

Problems

[edit]
Unsolved problem in computer science
⁠⁠
More unsolved problems in computer science

All problems in P are obviously also in BPP. However, many problems have been known to be in BPP but not known to be in P. The number of such problems is decreasing, and it is conjectured that P = BPP.

For a long time, one of the most famous problems known to be in BPP but not known to be in P was the problem of determining whether a given number is prime. However, in the 2002 paper PRIMES is in P, Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena found a deterministic polynomial-time algorithm for this problem, thus showing that it is in P.

An important example of a problem in BPP (in fact in co-RP) still not known to be in P is polynomial identity testing, the problem of determining whether a polynomial is identically equal to the zero polynomial, when you have access to the value of the polynomial for any given input, but not to the coefficients. In other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, the result is nonzero? It suffices to choose each variable's value uniformly at random from a finite subset of at least d values to achieve bounded error probability, where d is the total degree of the polynomial.[2]

[edit]

If the access to randomness is removed from the definition of BPP, we get the complexity class P. In the definition of the class, if we replace the ordinary Turing machine with a quantum computer, we get the class BQP.

Adding postselection to BPP, or allowing computation paths to have different lengths, gives the class BPPpath.[3] BPPpath is known to contain NP, and it is contained in its quantum counterpart PostBQP.

A Monte Carlo algorithm is a randomized algorithm which is likely to be correct. Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time. This is compared to a Las Vegas algorithm which is a randomized algorithm which either outputs the correct answer, or outputs "fail" with low probability. 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. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time, but with very low probability.

Complexity-theoretic properties

[edit]
Diagram of randomised complexity classes
BPP in relation to other probabilistic complexity classes (ZPP, RP, co-RP, BQP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict.
Inclusions of complexity classes including P, NP, co-NP, BPP, P/poly, PH, and PSPACE

It is known that BPP is closed under complement; that is, BPP = co-BPP. BPP is low for itself, meaning that a BPP machine with the power to solve BPP problems instantly (a BPP oracle machine) is not any more powerful than the machine without this extra power. In symbols, BPPBPP = BPP.

The relationship between BPP and NP is unknown: it is not known whether BPP is a subset of NP, NP is a subset of BPP or neither. If NP is contained in BPP, which is considered unlikely since it would imply practical solutions for NP-complete problems, then NP = RP and PH ⊆ BPP.[4]

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, since we don't even know if P is a strict subset of PSPACE. BPP is contained in the second level of the polynomial hierarchy and therefore it is contained in PH. More precisely, the Sipser–Lautemann theorem states that . As a result, P = NP leads to P = BPP since PH collapses to P in this case. Thus either P = BPP or P ≠ NP or both.

Adleman's theorem states that membership in any language in BPP can be determined by a family of polynomial-size Boolean circuits, which means BPP is contained in P/poly.[5] Indeed, as a consequence of the proof of this fact, every BPP algorithm operating on inputs of bounded length can be derandomized into a deterministic algorithm using a fixed string of random bits. Finding this string may be expensive, however. Some weak separation results for Monte Carlo time classes were proven by Karpinski & Verbeek (1987a), see also Karpinski & Verbeek (1987b).

Closure properties

[edit]

The class BPP is closed under complementation, union, intersection, and concatenation.

Relativization

[edit]

Relative to oracles, we know that there exist oracles A and B, such that PA = BPPA and PB ≠ BPPB. Moreover, relative to a random oracle with probability 1, P = BPP and BPP is strictly contained in NP and co-NP.[6]

There is even an oracle in which ⁠⁠ (and hence ⁠⁠),[7] which can be iteratively constructed as follows. 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). Start with n=1. For every instance of the problem of length n fix oracle answers (see lemma below) to fix the instance output. Next, provide the instance outputs for queries consisting of the instance followed by kn-length string, and then treat output for queries of length ≤(k+1)n as fixed, and proceed with instances of length n+1.

Lemma—Given a problem (specifically, an oracle machine code and time constraint) in relativized ENP, for every partially constructed oracle and input of length n, the output can be fixed by specifying 2O(n) oracle answers.

Proof

The machine is simulated, and the oracle answers (that are not already fixed) are fixed step-by-step. There is at most one oracle query per deterministic computation step. For the relativized NP oracle, if possible fix the output to be yes by choosing a computation path and fixing the answers of the base oracle; otherwise no fixing is necessary, and either way there is at most 1 answer of the base oracle per step. Since there are 2O(n) steps, the lemma follows.

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. Also, we can ensure that for the relativized ENP, linear time suffices, even for function problems (if given a function oracle and linear output size) and with exponentially small (with linear exponent) error probability. Also, this construction is effective in that given an arbitrary oracle A we can arrange the oracle B to have PA≤PB and EXPNPA=EXPNPB=BPPB. Also, for a ZPP=EXP oracle (and hence ZPP=BPP=EXP<NEXP), one would fix the answers in the relativized E computation to a special nonanswer, thus ensuring that no fake answers are given.

Derandomization

[edit]

The existence of certain strong pseudorandom number generators is conjectured by most experts of the field. Such generators could replace true random numbers in any polynomial-time randomized algorithm, producing indistinguishable results. The conjecture that these generators exist implies that randomness does not give additional computational power to polynomial time computation, that is, P = RP = BPP. More strongly, the assumption that P = BPP is in some sense equivalent to the existence of strong pseudorandom number generators.[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. They also showed that P = BPP if the exponential-time hierarchy, which is defined in terms of the polynomial hierarchy and E as EPH, collapses to E; however, note that the exponential-time hierarchy is usually conjectured not to collapse.

Russell Impagliazzo and Avi Wigderson showed that if any problem in E, where

has circuit complexity 2Ω(n) then P = BPP.[10]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

BPP (complexity)

View on Grokipedia
from Grokipedia
In computational complexity theory, BPP (Bounded-error Probabilistic Polynomial time) is the complexity class consisting of decision problems that can be solved by a probabilistic Turing machine running in polynomial time, such that for every input, the probability of outputting the correct answer is at least 2/3 (or any fixed constant greater than 1/2).[1][2] The error probability in BPP can be reduced arbitrarily close to zero through repetition and majority voting, leveraging concentration bounds like Chernoff's inequality, without increasing the asymptotic time complexity beyond polynomial.[1][3] BPP contains the class P of deterministic polynomial-time solvable problems, since deterministic algorithms can ignore random bits, and it is contained within PSPACE, the class of problems solvable using polynomial space.[2] It also includes subclasses like RP (randomized polynomial time with one-sided error) and coRP (its complement), as well as ZPP (zero-error probabilistic polynomial time), where algorithms either output the correct answer or "fail" with low probability.[1][3] Furthermore, BPP is contained in the second level of the polynomial hierarchy, specifically Σ₂ᵖ ∩ Π₂ᵖ, and in P/poly, the class of problems solvable in polynomial time with polynomial-sized non-uniform advice.[1][2] BPP is regarded as capturing the practical notion of efficient computation, as many real-world algorithms, such as primality testing and polynomial identity testing, fall into this class and benefit from randomization to achieve polynomial-time performance with high reliability.[2] A major open question is whether P = BPP, which would imply that randomization does not provide additional computational power for polynomial-time decision problems; derandomization results show BPP ⊆ P under assumptions like the existence of pseudorandom generators, but unconditional proofs remain elusive.[1][2]

Definition and Formalization

Informal Overview

BPP, or bounded-error probabilistic polynomial time, is a complexity class that captures decision problems solvable by a probabilistic Turing machine running in polynomial time, where the probability of an incorrect answer is at most 1/3 for every input.[4] This bounded error distinguishes BPP from deterministic classes like P, allowing algorithms to use randomness to achieve efficiency on problems that might otherwise require more computational resources. The class was introduced by John Gill in 1977 as part of the foundational study of probabilistic computation models.[4] The key intuition behind BPP is that access to randomness enables efficient solutions to tasks such as approximate counting—estimating the number of solutions to a problem within a multiplicative factor—and sampling from complex distributions, which may not be feasible deterministically in polynomial time.[5] These capabilities highlight how probabilistic methods can extend beyond strict determinism, potentially addressing problems harder than those in P while maintaining practical efficiency. It is known that P is contained in BPP, since any deterministic polynomial-time algorithm can be viewed as a special case of a probabilistic one with zero error.[5] A notable feature of BPP is the ability to reduce error through amplification: by repeating the algorithm a polynomial number of times and taking the majority vote, the success probability can be boosted from at least 2/3 to exponentially small failure probability, such as 1 - 2^{-n}, without altering the class membership.[5] Whether BPP equals P remains an open question, central to understanding the power of randomness in computation.[6]

Formal Definition

The class BPP, or Bounded-error Probabilistic Polynomial time, consists of all decision problems that can be solved by a probabilistic Turing machine (PTM) running in polynomial time with a bounded error probability.[4] Formally, a language L⊆{0,1}∗L \subseteq \{0,1\}^* is in BPP if there exists a PTM MM and a polynomial pp such that MM runs in time O(p(∣x∣))O(p(|x|)) for every input xx, and for every x∈Lx \in L, the probability that MM accepts xx is at least 2/32/3, while for every x∉Lx \notin L, the probability that MM rejects xx is at least 2/32/3.[4][5] Here, the PTM MM operates by flipping unbiased coins (uniform random bits from the distribution UmU_m where m=p(∣x∣)m = p(|x|)) to choose between transition functions at each step, ensuring the randomness is uniform and the total computation time is polynomial in the input length n=∣x∣n = |x|.[4][5] An equivalent definition of BPP uses a deterministic polynomial-time Turing machine verifier: LL is in BPP if there exists a deterministic TM MM and a polynomial qq such that for a random string r∈{0,1}q(n)r \in \{0,1\}^{q(n)} drawn uniformly, the probability that M(x,r)M(x, r) correctly decides whether x∈Lx \in L is at least 2/32/3.[5] This formulation interprets the random bits as an auxiliary input to a deterministic machine, with the majority vote over all 2q(n)2^{q(n)} possible strings implicitly determining membership via the high-probability threshold.[5] The choice of the 2/32/3 success probability (or equivalently, error at most 1/31/3) is arbitrary and can be relaxed without changing the class BPP. For instance, BPP remains the same if the error is bounded by 1/2−1/poly(n)1/2 - 1/\mathrm{poly}(n) or made exponentially small, as error reduction (amplification) is possible via repetition and majority voting.[5] Specifically, if a PTM has base success probability p≥2/3p \geq 2/3, repeating the computation independently kk times and taking the majority vote yields success probability at least 1−e−k/81 - e^{-k/8}, by the Chernoff bound applied to the binomial distribution of successes.[5]
Pr⁡[∣1k∑i=1kXi−p∣>δ]≤e−2kδ2 \Pr\left[ \left| \frac{1}{k} \sum_{i=1}^k X_i - p \right| > \delta \right] \leq e^{-2k\delta^2}
for independent Bernoulli random variables XiX_i with Pr⁡[Xi=1]=p\Pr[X_i = 1] = p and deviation δ=1/6\delta = 1/6 to bound the error below 1/21/2, ensuring polynomial-time amplification since kk can be chosen as poly(n)\mathrm{poly}(n).[5]

Related Complexity Classes

Basic Relations to P, RP, and co-RP

The class P of problems solvable in deterministic polynomial time is contained in BPP, since any deterministic polynomial-time algorithm can be viewed as a probabilistic one that ignores its random bits and always outputs the correct answer with probability 1.[5] Similarly, P is contained in the randomized class RP, which in turn is contained in BPP; this inclusion holds because RP algorithms, which use randomness to accept yes-instances with high probability while always rejecting no-instances, can be amplified and simulated within BPP's two-sided error model by repeating runs and taking majorities.[5] The class RP is defined by probabilistic polynomial-time Turing machines with one-sided error: for inputs xx in the language, the machine accepts with probability at least $ \frac{2}{3} $, and for xx not in the language, it rejects with probability 1.[3] Analogously, P is contained in co-RP, and co-RP is contained in BPP.[5] The class co-RP consists of languages whose complements are in RP, meaning probabilistic polynomial-time machines that always accept yes-instances but accept no-instances only with probability at most $ \frac{1}{3} $; this one-sided error on the no-instances contrasts with BPP's allowance for bounded error on both yes- and no-instances, where the overall probability of a correct decision is at least $ \frac{2}{3} $.[7] Unlike RP and co-RP, which have asymmetric error profiles, BPP's symmetric two-sided error enables straightforward amplification via repetition to reduce error probabilities exponentially.[5] A fundamental symmetry in BPP is its closure under complementation: BPP = co-BPP.[5] This equality arises because, for any BPP machine deciding a language LL, the complemented machine—obtained by swapping accept and reject states—decides the complement L‾\overline{L} with the same error bound, as the probabilities of error on yes- and no-instances are treated equivalently.[3] Despite these inclusions, key equalities remain unresolved: it is unknown whether P = BPP, and whether RP = BPP or co-RP = BPP.[](https:// theory.cs.princeton.edu/complexity/bppchap.pdf) No unconditional separations between P and BPP, or between RP and BPP, are known, leaving the exact position of BPP in the hierarchy of probabilistic classes an open problem.[7]

Advanced Relations to NP, PP, and PH

The class BPP is contained in PP because probabilistic Turing machines for BPP accept with probability at least $ \frac{2}{3} $ on yes-instances and reject with probability at least $ \frac{2}{3} $ on no-instances, which exceeds the majority threshold of $ \frac{1}{2} $ required for PP, allowing the error in PP's majority vote to approach but not exceed $ \frac{1}{2} - \epsilon $ for some $ \epsilon > 0 $.[8] This inclusion highlights BPP's bounded two-sided error as a stricter condition than PP's unbounded error, positioning BPP as a subclass where randomization provides efficient approximation with controlled risk. A key relation exists between BPP and NP: if NP $ \subseteq $ BPP, then the polynomial hierarchy PH collapses to its second level, $ \Sigma_2^p $. This follows from the Sipser-Gács-Lautemann theorem, which places BPP within $ \Sigma_2^p \cap \Pi_2^p \subseteq $ PH, and extends via inductive arguments on the hierarchy structure, implying that nondeterministic verification can be simulated by bounded-error probabilistic computation without expanding the hierarchy beyond two alternations.[9] The result underscores the improbability of NP $ \subseteq $ BPP, as it would resolve major open questions in complexity theory by dramatically simplifying PH.[10] Unconditionally, BPP is contained in PH, specifically within the second level $ \Sigma_2^p \cap \Pi_2^p $, via the Sipser-Gács-Lautemann theorem, which constructs an Arthur-Merlin protocol (MA) simulation of BPP using existential and universal quantifiers over polynomial-time verifiable predicates.[10] This inclusion relativizes, meaning it holds relative to any oracle, with no known oracle separations where BPP^A \not\subseteq PH^A, reflecting the robustness of the proof technique based on amplification and interactive proofs. The exact position of BPP within PH remains of interest, but the containment provides a firm upper bound short of PSPACE. BPP is also contained in PSPACE, achieved by deterministically enumerating all $ 2^{p(n)} $ possible random strings of polynomial length $ p(n) $ for a BPP machine running in time $ O(n^k) $, computing the fraction of accepting paths using a polynomial-space counter (storing values up to $ 2^{p(n)} $ in $ p(n) $ bits), and simulating each path in polynomial space and exponential time, which fits within PSPACE's polynomial-space bound allowing exponential runtime.[11] Toda's theorem further connects these classes by showing PH $ \subseteq $ P^{#P}, the class of problems solvable in polynomial time with oracle access to #P (exact counting). Since BPP $ \subseteq $ PH, this implies BPP $ \subseteq $ P^{#P} indirectly, linking bounded-error randomization to counting complexity; however, stronger unconditional placements like BPP $ \subseteq \Delta_2^p $ (P^{NP}) require assumptions such as the existence of hard functions for NP or circuit lower bounds, as in conditional derandomization results.[12]

Example Problems and Applications

Natural Problems in BPP

One prominent natural problem in BPP is polynomial identity testing (PIT), which determines whether two given multivariate polynomials over a field are identical. A randomized algorithm for PIT relies on the Schwartz-Zippel lemma, which states that if two polynomials of total degree at most dd agree on all points from a finite subset SS of the field with ∣S∣>d|S| > d, then they are identical; otherwise, the probability that a random evaluation point from SnS^n (where nn is the number of variables) yields the same value when the polynomials differ is at most d/∣S∣d/|S|.[13] By repeating the evaluation sufficiently many times, the error probability can be reduced to exponentially small, placing PIT in co-RP and hence in BPP, since co-RP ⊆\subseteq BPP.[14][15] However, it remains unknown whether PIT lies in P, making it a canonical example of a problem where randomization provides practical efficiency without a known deterministic polynomial-time solution.[16] Another class of natural problems in BPP involves approximate counting and sampling, particularly for estimating the number of solutions to combinatorial problems like the number of satisfying assignments to a Boolean formula (#SAT). Using the framework of Jerrum, Valiant, and Vazirani, approximate counting for self-reducible #P problems can be achieved via Markov chain Monte Carlo (MCMC) methods, such as random walks on an appropriate state space, to sample nearly uniformly and estimate the count within a multiplicative factor of 1±ϵ1 \pm \epsilon with high probability in randomized polynomial time relative to an oracle for the decision problem.[17] For #SAT specifically, this places approximate counting in BPPNP^{\text{NP}}, but the randomized nature highlights BPP's utility for approximation where exact counting is #P-complete and deterministic approximation is NP-hard.[18] These techniques extend to sampling satisfying assignments, enabling applications in probabilistic inference and statistical mechanics.[19] Graph non-isomorphism, the problem of deciding whether two given graphs are not isomorphic, provides another illustrative example, though its precise placement relative to BPP is subtle. It is known to be in co-AM via an interactive proof system where the verifier randomly permutes one graph and challenges the prover to identify the isomorphism, succeeding with high probability if the graphs differ.[20] While co-AM is not known to be contained in BPP, the problem admits randomized algorithms using random mappings to generate isomorphism tests with bounded error, suggesting practical computability in the spirit of BPP, and it is contained in co-BP⋅\cdotNP.[21] This contrasts with graph isomorphism, whose deterministic complexity remains open beyond quasi-polynomial time. Historically, primality testing exemplifies a problem that resided in BPP before advancing to P. The Solovay-Strassen test from 1977 uses random witnesses to verify Euler's criterion and Jacobi symbols, accepting primes with probability 1 and composites with probability at most 1/2 per trial, thus placing primality in BPP after amplification.[22] Similarly, the Miller-Rabin test from 1976-1980 employs random bases to check Fermat-like conditions, also in co-RP ⊆\subseteq BPP, and is widely used in practice due to its efficiency.[23] The 2002 AKS algorithm later proved primality is in P via deterministic checks on polynomial congruences, demonstrating how BPP can bridge gaps in deterministic complexity until resolved.[24] In recent applications, particularly in machine learning, approximate nearest neighbor (ANN) search in high-dimensional spaces emerges as a natural BPP problem. Algorithms like locality-sensitive hashing (LSH) preprocess a point set using random projections or hash functions to bucket similar points, enabling queries to retrieve an approximate nearest neighbor within factor c>1c > 1 with constant success probability, improvable by repetition to place the (decision) problem in BPP.[25] This is crucial for tasks like recommendation systems and image retrieval, where exact search is intractable in high dimensions due to the curse of dimensionality, but randomized approximations scale efficiently.[26]

Complete Problems for BPP

Unlike other complexity classes such as NP, which possess natural complete problems like SAT under polynomial-time reductions, no natural complete problems are known for BPP.[5] This absence stems from BPP's semantic definition in terms of bounded-error probabilistic computation, which complicates the identification of problems that capture the full power of the class without additional restrictions.[5] To address this, researchers have turned to artificial constructions, particularly within the framework of promise problems. A canonical example is the promise problem for BPP defined using Boolean circuits: the yes-instances consist of circuits that evaluate to 1 on at least a 2/3 fraction of their inputs, while the no-instances are circuits that evaluate to 0 on at least a 2/3 fraction of inputs, with the promise excluding circuits where the acceptance fraction falls strictly between 1/3 and 2/3. This problem is complete for the class of promise problems solvable in BPP (Promise-BPP) under deterministic polynomial-time Karp reductions.[27] A similar completeness holds for the analogous promise problem based on probabilistic Turing machines: given a machine description M, input x, and time bound 1^p (where p is polynomial in |x|), promise that the acceptance probability of M on x is either at most 1/3 or at least 2/3 within time p, and decide which case holds; this is also Promise-BPP-complete under polynomial-time reductions.[27] An analogous artificial complete problem can be formulated using satisfiability: consider the promise version of Majority-SAT where, for a given Boolean formula φ on n variables, it is promised that the fraction of satisfying assignments is either less than 1/3 or greater than 2/3, and the task is to decide which. This promise problem is BPP-complete under Cook reductions, as probabilistic sampling can approximate the fraction with high confidence, and general BPP computations can be encoded into such formulas via reductions.[28] Other candidates for natural BPP-complete problems, such as parity games and approximate shortest paths in undirected graphs with exponential weights, have been proposed due to their placement in BPP and potential hardness, but completeness remains unproven. Theoretical constructions of complete problems for BPP can also employ diagonalization techniques or adaptations of Levin's universal search to the probabilistic setting, yielding generic complete languages that enumerate over all probabilistic machines.[27] The existence of complete problems for BPP carries significant implications for derandomization: if a BPP-complete language (under polynomial-time reductions) could be derandomized to lie in P, then the closure of P under such reductions would imply P = BPP.[5]

Complexity-Theoretic Properties

Closure Properties

BPP exhibits several desirable closure properties under standard complexity-theoretic operations, reflecting its robustness as a probabilistic complexity class. One fundamental closure is under complementation: for any language L∈L \in BPP, its complement L‾\overline{L} is also in BPP. This follows directly from the definition, as a probabilistic Turing machine deciding LL with error probability at most 1/31/3 can be modified by swapping the accept and reject states, preserving the error bound since the success probability for L‾\overline{L} becomes at least 2/32/3 as well.[5] BPP is also closed under finite unions and intersections computable in polynomial time. For the union of two languages L1,L2∈L_1, L_2 \in BPP, a probabilistic Turing machine can run the machines for L1L_1 and L2L_2 independently on the input using fresh random bits, accepting if at least one accepts. Without amplification, the error probability is at most 1/3+1/3=2/31/3 + 1/3 = 2/3, but repeated independent runs and majority voting amplify the success probability to exceed 2/32/3, ensuring the result remains in BPP. A similar construction applies to intersections by accepting only if both machines accept, with amplification handling the additive error. These closures extend to polynomially many such operations via parallel simulation.[5][29] Regarding composition, BPP is closed under relativization to itself: if L1∈L_1 \in BPP and L2∈L_2 \in BPPL1^{L_1}, then L2∈L_2 \in BPP. This holds because a machine for L2L_2 can query the oracle for L1L_1 using polynomially many calls, and each query can be simulated by the probabilistic machine for L1L_1 with independent random bits, maintaining the overall error probability below 1/31/3 after amplification to account for multiple simulations. The BP Interchange Lemma formalizes this by showing that bounded-error probabilistic oracle classes compose within BPP when the oracle class supports polynomial-time reductions.[29] However, BPP is not known to be closed under Turing reductions to classes harder than BPP, such as NP. For instance, whether BPPNP=^{\text{NP}} = BPP remains an open question, as simulating NP oracles probabilistically may require additional randomness or power beyond standard BPP machines. Such non-closures highlight limitations in derandomizing or extending probabilistic computations to nondeterministic settings without increasing complexity.[29]

Relativization and Oracle Separations

The Baker-Gill-Solovay theorem establishes that the standard diagonalization techniques used to prove complexity class separations relativize, meaning they hold relative to arbitrary oracles A. Consequently, these techniques cannot resolve the open question of whether P = BPP in the unrelativized setting, as there exist oracles relative to which the equality holds and others relative to which it does not.[30] Relative to a PSPACE-complete oracle A, P^A = BPP^A holds, since BPP^A ⊆ PSPACE^A = P^A (with the latter equality following from the completeness of A under polynomial-time reductions). Relative to a random oracle A, P^A = BPP^A with probability 1 over the choice of A, as probabilistic computations can be deterministically simulated using the pseudorandom properties of the oracle bits.[31][31] In contrast, there exist oracles B relative to which P^B ≠ BPP^B, demonstrating that BPP^B ⊈ P^B. One such construction diagonalizes against all polynomial-time probabilistic machines to ensure that a carefully defined language lies in BPP^B but requires superpolynomial time relative to P^B. A specific example is an oracle where P^B = RP^B but RP^B ≠ BPP^B, implying P^B ≠ BPP^B since RP^B ⊆ BPP^B. These oracle results highlight fundamental barriers to proving P = BPP using relativizing proof techniques, necessitating non-relativizing methods—such as those involving arithmetization or limited interaction—for progress on derandomization. Post-2000 refinements have explored conditional oracle separations under hardness assumptions, extending earlier derandomization insights to relativized settings with nonuniform advice.

Derandomization Results

Unconditional Results and Limitations

One of the earliest unconditional derandomization results for BPP is Adleman's theorem, which establishes that BPP is contained in P/poly, the class of languages decidable by nonuniform polynomial-time algorithms with polynomial-sized advice. This result shows that any language in BPP can be decided by a family of polynomial-sized circuits, one for each input length, effectively derandomizing BPP at the cost of non-uniformity. The proof relies on the probabilistic method and Chernoff bounds to demonstrate that a sufficiently large set of random strings can be "fixed" by non-uniform advice to simulate the randomized computation with high probability, fooling the randomness without needing uniform deterministic efficiency. Further unconditional progress has been made in partial derandomization, particularly for space-bounded computations within BPP. Nisan constructed a pseudorandom generator that stretches O(S log R) truly random bits into R pseudorandom bits indistinguishable by any algorithm running in space S, thereby derandomizing randomized space-bounded computations. This generator, based on the structure of computation graphs in space-bounded Turing machines, reduces the randomness complexity from polynomial to nearly linear in the space bound times the logarithm of the computation length. Extensions of this approach to time-bounded settings provide limited unconditional derandomization for restricted classes, such as logarithmic space, but do not fully resolve general BPP. Despite these advances, full unconditional derandomization of BPP—placing it squarely in P—remains unresolved, with no known deterministic polynomial-time algorithm for general BPP languages. Moreover, black-box proof techniques using generic pseudorandom generators face inherent barriers, as shown by Impagliazzo and Wigderson, who demonstrated that such methods cannot derandomize BPP without additional non-black-box assumptions or hardness hypotheses. These limitations highlight the challenges in eliminating randomness uniformly and efficiently. Historical unconditional results also include early probabilistic algorithms for specific problems in BPP, such as polynomial identity testing (PIT), where Schwartz developed a fast randomized test that verifies whether two multivariate polynomials are identical by evaluating them at random points, succeeding with high probability in polynomial time. This approach, relying on the Schwartz-Zippel lemma, provided an early demonstration of BPP's power for natural algebraic problems, though full derandomization of general PIT remains tied to circuit lower bounds.

Conditional Derandomization

Conditional derandomization of BPP relies on assumptions about the hardness of computing functions in exponential time against small circuits. The foundational result in this area is the Impagliazzo–Wigderson framework, which establishes that if every language in the complexity class E = DTIME[2^{\Omega(n)}] requires Boolean circuits of size 2^{\Omega(n)}, then P = BPP.[32] This is achieved by constructing pseudorandom generators (PRGs) that stretch a short seed of length O(\log n) into a pseudorandom string of polynomial length, which can replace the random bits in any BPP algorithm while preserving correctness with high probability.[32] Central to this framework is the Nisan–Wigderson generator, which builds a PRG from any sufficiently hard function in E that cannot be computed by circuits of subexponential size.[33] Given a function f that is hard for circuits of size s on inputs of length l = \Omega(\log s), the generator produces m pseudorandom bits that fool any circuit of size s with advantage at most \epsilon, using a seed of length d = O(\log^2 (m / \epsilon)).[33] The construction designs a set of test spaces that ensure the output distribution is indistinguishable from uniform randomness for the target circuit class.[33] Subsequent extensions refined these parameters to near-optimal levels. Umans showed how to construct PRGs converting s bits of hardness into s^{\Omega(1)} bits of two-sided pseudorandomness, achieving the best possible stretch under the hardness assumption and enabling efficient derandomization of BPP with minimal overhead.[34] Further work by Umans introduced reconstructive dispersers, leading to hitting set generators for polynomial identity testing (PIT), which derandomize randomized algorithms for verifying polynomial identities under algebraic circuit hardness assumptions.[35] Advances from 2022 explored characterizations of BPP derandomization through the lens of Levin–Kolmogorov complexity, linking it to the hardness of finding short programs via universal search. Specifically, results show that derandomizing BPP is equivalent to average-case hardness for minimum KT complexity (a variant of Levin's universal search problem), offering progress toward understanding conditional separations without strong circuit lower bounds.[36] More recent work in 2023 by Chen, Tell, and Williams established a unified framework showing that derandomization of BPP is equivalent to constructive lower bounds against multi-output algorithms for refutation tasks.[37] In 2025, Ball, Chen, and Tell advanced free lunch derandomization—derandomizing without asymptotic time overhead—from natural hardness assumptions over polynomial-time samplable distributions, including those implying one-way functions, using superfast targeted generators.[38]

Connections to Broader Complexity Classes

Relation to Quantum Complexity Classes

The class BPP is contained in BQP, as quantum computers can efficiently simulate classical probabilistic computations by generating random bits through quantum superposition and measurement, preserving the bounded-error property within polynomial time. While BQP is believed to be strictly larger than BPP, no unconditional separation has been proven between the two classes. For example, integer factoring is in BQP via Shor's algorithm but is not known to be in BPP.[39] Quantum pseudorandom generators, explored in works by Aaronson in the 2000s, offer potential for derandomizing BPP computations more efficiently than classical methods under cryptographic assumptions, by leveraging quantum states that appear random to classical probabilistic algorithms. Recent quantum supremacy experiments, such as Google's 2019 demonstration using a 53-qubit processor to perform random circuit sampling beyond the reach of classical supercomputers, underscore the practical limits of simulating BQP tasks with BPP algorithms, though no new theoretical separations between BPP and BQP have emerged as of 2025.[40] If BQP were contained in P/poly, then BPP would also be contained in P/poly; this follows from the known inclusion BPP ⊆ BQP and Adleman's theorem establishing BPP ⊆ P/poly unconditionally.[41]

Links to Circuit Complexity and Lower Bounds

It is a fundamental result in complexity theory that BPP ⊆ P/poly, where P/poly denotes the class of problems solvable by non-uniform families of polynomial-size Boolean circuits. This inclusion holds unconditionally and follows from Adleman's theorem, which uses the probabilistic method and isolating lemmas to construct, for any language in BPP, a non-uniform advice string of polynomial length that simulates the probabilistic computation deterministically.[41] A key connection between BPP and circuit complexity arises in derandomization efforts, where circuit lower bounds imply the collapse of BPP to P. Specifically, if every language in E = DTIME(2^{O(n)}) requires exponential-size circuits (i.e., E ⊈ P/poly), then pseudorandom generators suffice to derandomize BPP, yielding P = BPP; this is the core of the Impagliazzo-Wigderson paradigm, which derandomizes the XOR lemma under this hardness assumption. Conversely, assuming P = BPP implies superpolynomial circuit lower bounds for E, as shown by Kabanets and Impagliazzo, establishing a tight bidirectional link between derandomizing BPP and proving lower bounds against non-uniform polynomial-size circuits. BPP, being a uniform complexity class, is contained in the non-uniform class P/poly, but the two models exhibit separations in relativized worlds and under certain assumptions. For instance, oracle separations demonstrate that uniform and non-uniform hierarchies can diverge, with BPP potentially requiring more uniformity than P/poly allows in some relativized settings; however, the unconditional inclusion highlights how non-uniformity can "absorb" the randomness in BPP computations. Recent advances (2020–2025) have strengthened these links by exploring derandomization of space-bounded classes, yielding insights into BPP. For example, progress on derandomizing logarithmic-space probabilistic computation, including hitting sets and spectral methods for graph Laplacians, has implications for broader BPP derandomization by providing conditional pseudorandom objects that extend to time-bounded settings.[42] Additionally, results on derandomizing RL using algebraic techniques have advanced understanding of space-bounded derandomization with relevance to time classes like BPP.[43] Post-2011 circuit results have further connected BPP to separations against restricted circuit classes like ACC^0 (constant-depth circuits with modulo gates). Building on Williams' non-uniform NEXP ⊈ ACC^0[poly] bound, subsequent works using the algorithmic method have derived almost-everywhere lower bounds for ACC^0 from non-trivial derandomizations, implying that derandomizing BPP would require even stronger separations against these efficient circuit families.

References

  1. [PDF] Probabilistic Complexity Classes 1 Introduction
  2. [PDF] Handout 7 1 More on Randomized Complexity Classes
  3. [PDF] 2.1 Complexity Classes
  4. Computational Complexity of Probabilistic Turing Machines
  5. [PDF] Computational Complexity: A Modern Approach - Princeton University
  6. P vs. BPP - Open Problem Garden
  7. [PDF] Lecture 6: Randomized Algorithms, Properties of BPP
  8. [PDF] Probabilistic Complexity Classes - University of Waterloo
  9. [PDF] Classes of problems with probabilistic algorithms - UCSD CSE
  10. [PDF] Another proof that BPP ⊆ PH (and more)
  11. [PDF] Theory of Computation
  12. [PDF] Toda's Theorem: PH ⊆ P
  13. [PDF] Lecture 7: Schwartz-Zippel Lemma, Perfect Matching - Washington
  14. [PDF] Lecture 2: Randomized Algorithms 1 Polynomial Identity Testing
  15. [PDF] Lecture 1: August 29 1.1 Introduction: Polynomial Identity Testing
  16. [PDF] Lecture 9 1 Polynomial Identity Testing - UBC Computer Science
  17. [PDF] Approximate Model Counting - cs.Toronto
  18. [PDF] Lecture 24 Computational Complexity Theory - CSA – IISc Bangalore
  19. [PDF] The Power of Randomness - Harvard SEAS
  20. [PDF] Lecture 17 1 Graph Non-Isomorphism is in AM
  21. [PDF] 1 Graph Non-Isomorphism - CS-People by full name
  22. [PDF] Primality Testing∗ - Mathematical Sciences Institute, ANU
  23. [PDF] Solovay-Strassen and Miller-Rabin Primality Tests - TigerWeb
  24. [PDF] Notes on Primality Testing And Public Key Cryptography Part 1
  25. Approximate Nearest Neighbor Search in High Dimensions - arXiv
  26. [PDF] Approximate Nearest Neighbor Search in High Dimensions
  27. [PDF] On Promise Problems - Faculty of Mathematics and Computer Science
  28. [PDF] Promise problems 1 Definitions and examples - TAU
  29. [PDF] On Closure Properties of Bounded 2-Sided Error Complexity Classes
  30. Relativizations of the P = ? NP Question - SIAM Publications Library
  31. [PDF] RELATIVE TO A RANDOM ORACLE A, # pA and PSPACEA ...
  32. [PDF] Derandomizing from Random Strings - Lance Fortnow
  33. [PDF] P=BPP unless E has sub-exponential circuits: Derandomizing the ...
  34. Hardness vs randomness - ScienceDirect.com
  35. Pseudo-random generators for all hardnesses - ScienceDirect.com
  36. [PDF] Reconstructive Dispersers and Hitting Set Generators - Caltech
  37. [PDF] BQP and the Polynomial Hierarchy - Scott Aaronson
  38. Complexity Zoo:B
  39. Oblivious Complexity Classes Revisited: Lower Bounds and ... - arXiv
User Avatar
No comments yet.