## ZPP

A class of randomized algorithms (i.e. algorithms which also utilise a stream of random bits). They are essentially what physicists call Las Vegas 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 ZPP (A∈ZPP) iff:

For the name: think "**Z**ero **P**robability of error, (expected) **P**olynomial running time". Sorry.

As an example, the median selection algorithm based on Quick Sort (when pivots are chosen at random, the "usual" form in textbooks) is a ZPP algorithm: it *always* gets the right anwer, and the expected running time is O(n). However, *some* runs may require much longer.

Compare: P, BPP, NP, co-NP, RP, co-RP.