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 "Zero Probability of error, (expected) Polynomial 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.