A class of randomized algorithms (i.e. algorithms which also utilise a stream of random bits). They are essentially what physicists call Monte Carlo Algorithms, although possibly better-defined in the language of complexity theory.
A randomized algorithm A for computing a function f(x) is said to be in BPP (A∈BPP) iff:
The `1/3' in the first part is fairly arbitrary (this put here mostly to silence the annoying little guy in the front row who just took his Introduction to Randomized Algorithms course the last semester). Any constant probability that is bounded away from 1/2 may be amplified to get 1/3; indeed, the entire range from polylogarithmic to (poly-)exponentially small probability of error give the same class.
For the name: think "Bounded Probability of error, (expected) Polynomial running time". Sorry.
Of course P⊆ZPP⊆BPP. It is also known that BPP⊆Π2∩Σ2 (the second stage of the polynomial hierarchy). It is not known whether NP⊆ZPP, or even whether ZPP⊆NP (however, the latter would be even more surprising than the former!).
The "polynomial hierarchy" stuff above means that if L∈BPP is a language
, then there exist formula
e f(x,y,z) and g(x,y,z) such that
- ∀x.(x∈L ↔ ∃y.∀z.f(x,y,z))
- ∀x.(x∈L ↔ ∀y.∃z.g(x,y,z))
Despite this formidable armour, most "randomized algorithms" out there are in BPP.