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$.

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