Types of algorithms:
- Monte Carlo algorithms
- may return an answer that is not
correct.
Example: primality testing
Subtypes: one-sided vs. two-sided errors
- Las Vegas algorithms
- may not return an answer at all, but
if they do the answer is guaranteed to be correct.
Example: factoring
- Sherwood algorithms
-
- always give the correct answer.
(Sometimes also called Las Vegas.)
Example: Quicksort
Complexity classes:
- Randomized Polynomial time (RP):
- A language is in RP if there is a polynomial-time (Monte Carlo) algorithm
that never accepts words that are not in the language, and
has probability at least 1/2 of accepting words in the language
- Zero-error Probabilistic Polynomial (ZPP)
- Like RP, except the algorithm is Sherwood, so it always accepts
if the word is in the language
- Bounded-error Probabilistic Polynomial (BPP)
- Like RP, except that the algorithm has probability at least 3/4 of
accepting if the word is in the language, and probability at most 1/4
of accepting if the word is not in the language.
References:
Algorithmics, by Gilles Brassard and Paul Bratley,
Prentice Hall, 1988
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan,
Cambridge University Press, 1995