bpp

Bits Per Pixel, or bitdepth, color depth in bits...

1 bpp would be monochrome. 24 and 32 bpp are easy to work with as far as colors go, because you'd typically get a byte for red, green, and blue. For lower depths, colors get more complicated, or less complicated if you're using a static color map.

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:

• P(A(x)!=f(x)) < 1/3. (A is usually right!)
• The expected running time of A on input x with n=|x| is polynomial in n.

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⊆Π₂∩Σ₂ (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.