Las Vegas algorithm
From Wikipedia, the free encyclopedia
In computing, a Las Vegas algorithm is a randomized algorithm that is correct; that is, it always produces the correct result. In other words, a Las Vegas algorithm does not gamble with the verity of the result --- it only gambles with the resources used for the computation. A simple example is randomized quicksort, where the pivot is chosen randomly, but the result is always sorted. The usual definition of a Las Vegas algorithm includes the restriction that the expected run time always be finite, when the expectation is carried out over the space of random information, or entropy, used in the algorithm.
The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP.
It turns out that
which is intimately connected with the way Las Vegas algorithms are sometimes constructed. Namely the class RP consists of all decision problems for which a randomized polynomial-time algorithm exists that always answers correctly when the correct answer is "no", but is allowed to be wrong with a certain probability bounded away from one when the answer is "yes". When such an algorithm exists for both a problem and its complement (with the answers "yes" and "no" swapped), the two algorithms can be run simultaneously and repeatedly: a few steps of each, taking turns, until one of them returns a definitive answer. This is the standard way to construct a Las Vegas algorithm that runs in expected polynomial time. Note that in general there is no worst case upper bound on the run time of a Las Vegas algorithm.
Las Vegas algorithms can be contrasted with Monte Carlo algorithms, in which the resources used are bounded but the final result may not be 100% accurate.
