Las Vegas algorithm

A Las Vegas algorithm is a randomized algorithm that always returns a correct result when it terminates. The term was introduced in 1979 by László Babai in connection with graph isomorphism as a variant of Monte Carlo algorithms .

There are two definitions of Las Vegas algorithms and their time complexity :

• If the random bits only have an influence on the procedure of the algorithm, the Las Vegas algorithm always delivers a correct result when it terminates.
  The time complexity in this case depends on a random variable. A well-known example is the random quicksort algorithm , which chooses its pivot element at random, but whose output is always sorted.
• If the result of the calculation of an algorithm with a probability is correct and at the same time the algorithm with a probability does not produce a result, then it is a Las Vegas algorithm. ${\displaystyle \geq {\frac {1}{2}}}$ ${\displaystyle \leq {\frac {1}{2}}}$

See also

• Randomized complexity classes

Individual evidence

1. ↑ Juraj Hromkovič : Randomized Algorithms . Methods for designing random systems for beginners. 1st edition. Teubner, 2004, ISBN 3-519-00470-4 , pp. 67 .
2. ^ László Babai : Monte-Carlo algorithms in graph isomorphism testing. (PDF; 232 kB) Accessed December 12, 2012 (English). 
3. ↑ Juraj Hromkovič : Randomized Algorithms . Methods for designing random systems for beginners. 1st edition. Teubner, 2004, ISBN 3-519-00470-4 , pp. 67 f .