## BPP

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 "**B**ounded **P**robability of error, (expected) **P**olynomial 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

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