BPP

This article defines a decision complexity class, i.e., a complexity class for decision problems. This means that given any language, the language is either a member of the decision complexity class or it is not a member of the decision complexity class.| View a list of complexity classes

Definition

BPP or bounded-error probabilistic polynomial time is a complexity class that can loosely be described as the class of languages in which membership can be decided using a randomized algorithm that runs in polynomial time, with the probability of error either way bounded by a number less than $1/2$.

Using $2/3$ and $1/3$

More formally, a language $L$ is in BPP if there exist functions $f$ and $g$ growing polynomially in their inputs, such that for any string of length $n$, the algorithm uses the string and a random string of length $f(n)$ to output, in time at most $g(n)$, whether the string is in $L$, and the answer satisfies the following: For every choice of input string, less than $1/3$ of the possible random strings of length $f(n)$ give the wrong answer.

Note that the probability is taken over the random string and not over the input string. For the input string, we are interested in the worst case probability, i.e., we would like a low error probability for all input strings.

Relation with other complexity classes

Larger complexity classes

Complexity class	Meaning	Proof of containment	Reverse containment -- separation result or open problem	Intermediate complexity classes
PP	probabilistic polynomial time; like BPP but probability of giving the correct output is allowed to equal $1/2$	PP contains BPP
P/poly	For any fixed input length, there is a polynomial sized advice string depending on the length, using which a polynomial time algorithm can be devised for all inputs of that length.	Adleman's theorem	Separated: P/poly contains undecidable languages	click here
Sigma2P	$\Sigma _{2}$ in the polynomial hierarchy	part of the Sipser-Lautemann theorem	open, but if true, would imply that NP is in P/poly and hence PH collapses to BPP	click here
Pi2P	$\Pi _{2}$ in the polynomial hierarchy	part of the Sipser-Lautemann theorem	open, but if true, would imply that NP is in P/poly and hence PH collapses to BPP	click here
Sigma2P intersect Pi2P	$\Sigma _{2}P\cap \Pi _{2}P$	Sipser-Lautemann theorem	open, but if true, would imply that NP is in P/poly and hence PH collapses to BPP	click here
PH	The union of the entire polynomial hierarchy	(via Sigma2P)	open	click here

Smaller complexity classes

Complexity class	Meaning	Proof of containment	Reverse containment -- separation result or open problem	Intermediate complexity classes
RP	randomized polynomial time -- no false positives, but possible false negatives	RP is in BPP	open	click here
co-RP	randomized polynomial time -- no false negatives, but possible false positives	co-RP is in BPP	open	click here
P	deterministic polynomial time	P is in BPP	open -- see P equals BPP conjecture	click here

Properties

Property	Satisfied?	Proof	Statement with symbols
self-complementary complexity class	Yes	BPP is self-complementary	If $L\in BPP$, then the complement $L^{c}$, defined as the set of strings not in $L$, is also in $BPP$.
determined by almost everywhere	Yes	?