In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s solvable by a
probabilistic Turing machine
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turin ...
in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
with an error
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
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 algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s 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 machine is a special case of a probabilistic machine.
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
A language ''L'' is in BPP if and only if there exists a
probabilistic Turing machine
In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turin ...
''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
Constant or The Constant may refer to:
Mathematics
* Constant (mathematics), a non-varying value
* Mathematical constant, a special number that arises naturally in mathematics, such as or
Other concepts
* Control variable or scientific const ...
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/2
100, 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
In probability theory, the Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. Despite being named after Herman Chernoff, the author of the paper it first appeared in, the result is d ...
.
Problems
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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
. However, in the 2002 paper ''
PRIMES is in P'',
Manindra Agrawal
Manindra Agrawal (born 20 May 1966) is a professor at the Department of Computer Science and Engineering and the Deputy Director at the Indian Institute of Technology, Kanpur. He was also the recipient of the first Infosys Prize for Mathematics ...
and his students
Neeraj Kayal and
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 In mathematics, polynomial identity testing (PIT) is the problem of efficiently determining whether two multivariate polynomials are identical. More formally, a PIT algorithm is given an arithmetic circuit that computes a polynomial p in a field, a ...
, 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.
Related classes
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
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algor ...
with a
quantum computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thoug ...
, we get the class
BQP
In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isaa ...
.
Adding
postselection In probability theory, to postselect is to condition a probability space upon the occurrence of a given event. In symbols, once we postselect for an event E, the probability of some other event F changes from \operatorname /math> to the conditional ...
to BPP, or allowing computation paths to have different lengths, gives the class BPP
path. BPP
path is known to contain NP, and it is contained in its quantum counterpart
PostBQP In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is corre ...
.
A
Monte Carlo algorithm
In computing, a Monte Carlo algorithm is a randomized algorithm whose output may be incorrect with a certain (typically small) probability. Two examples of such algorithms are Karger–Stein algorithm and Monte Carlo algorithm for minimum Feedb ...
is a
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performa ...
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 In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the ...
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

It is known that BPP is closed under
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
; that is, BPP = co-BPP. BPP is
low
Low or LOW or lows, may refer to:
People
* Low (surname), listing people surnamed Low
Places
* Low, Quebec, Canada
* Low, Utah, United States
* Lo Wu station (MTR code LOW), Hong Kong; a rail station
* Salzburg Airport (ICAO airport code: LO ...
for itself, meaning that a BPP machine with the power to solve BPP problems instantly (a BPP
oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
) is not any more powerful than the machine without this extra power. In symbols, BPP
BPP = BPP.
The relationship between BPP and
NP is unknown: it is not known whether BPP is a
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problems, then NP = RP and
PH ⊆ BPP.
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
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...
and therefore it is contained in PH. More precisely, the
Sipser–Lautemann theorem
In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) time is contained in the polynomial time hierarchy, and more specifically Σ2 ∩ Π2. ...
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 circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible in ...
s, which means BPP is contained in
P/poly
In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equiva ...
. 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 , see also .
Closure properties
The class BPP is closed under complementation, union and intersection.
Relativization
Relative to oracles, we know that there exist oracles A and B, such that P
A = BPP
A and P
B ≠ BPP
B. Moreover, relative to a
random oracle
In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time tha ...
with probability 1, P = BPP and BPP is strictly contained in NP and co-NP.
There is even an oracle in which BPP=EXP
NP (and hence P<NP<BPP=EXP=NEXP), 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 E
NP, for every partially constructed oracle and input of length ''n'', the output can be fixed by specifying 2
''O''(''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 2
''O''(''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 E
NP answers. Also, we can ensure that for the relativized E
NP, 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 P
A≤P
B and EXP
NPA=EXP
NPB=BPP
B. 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
The existence of certain strong
pseudorandom number generators
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generate ...
is
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...
d by most experts of the field. This conjecture implies that randomness does not give additional computational power to polynomial time computation, that is, P = RP = BPP. Note that ordinary generators are not sufficient to show this result; any probabilistic algorithm implemented using a typical random number generator will always produce incorrect results on certain inputs irrespective of the seed (though these inputs might be rare).
László Babai
László "Laci" Babai (born July 20, 1950, in Budapest) a fellow of the American Academy of Arts and Sciences, and won the Knuth Prize.
Babai was an invited speaker at the International Congresses of Mathematicians in Kyoto (1990), Zürich (1994 ...
,
Lance Fortnow
Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology.
Biogra ...
,
Noam Nisan
Noam Nisan ( he, נעם ניסן; born June 20, 1961) is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game t ...
, and
Avi Wigderson
Avi Wigderson ( he, אבי ויגדרזון; born 9 September 1956) is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jerse ...
showed that unless
EXPTIME
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2''p''(''n'')) time, ...
collapses to
MA, BPP is contained in
:
The class i.o.-SUBEXP, which stands for infinitely often SUBEXP, contains problems which have
sub-exponential time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
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
In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...
and E as E
PH, collapses to E; however, note that the exponential-time hierarchy is usually conjectured ''not'' to collapse.
Russell Impagliazzo
Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego specializing in computational complexity theory, having joined the faculty of UCSD in 1989. He received a BA in mathematics from Wesleyan U ...
and Avi Wigderson showed that if any problem in
E, where
:
has circuit complexity 2
Ω(''n'') then P = BPP.
[Russell Impagliazzo and Avi Wigderson (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma". ''Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing'', pp. 220–229. ]
See also
*
RP
*
ZPP
*
BQP
In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isaa ...
*
List of complexity classes
This is a list of complexity classes in computational complexity theory. For other computational and complexity subjects, see list of computability and complexity topics.
Many of these classes have a 'co' partner which consists of the complemen ...
References
*
Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University
Simon Fraser University (SFU) is a public research university in British Columbia, Canada, with three campuses, all in Greater Vancouver: Burnaby (main campus), Surrey, and Vancouver. The main Burnaby campus on Burnaby Mountain, located ...
.
* Pages 257–259 of section 11.3: Random Sources. Pages 269–271 of section 11.4: Circuit complexity.
* Section 10.2.1: The class BPP, pp. 336–339.
*
*
* Arora, Sanjeev; Boaz Barak (2009). "Computational Complexity: A Modern Approach".
External links
Princeton CS 597E: Derandomization paper listHarvard CS 225: Pseudorandomness
{{DEFAULTSORT:Bpp
Probabilistic complexity classes