Las Vegas Algorithm
(Redirected from Las Vegas Randomized Algorithm)
Jump to navigation
Jump to search
A Las Vegas Algorithm is a randomized algorithm is a correct results generating algorithm.
- See: Monte-Carlo Algorithm.
References
2013
- http://en.wikipedia.org/wiki/Las_Vegas_algorithm
- In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the correctness of the result; it gambles only 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.
Las Vegas algorithms were introduced by László Babai in 1979, in the context of the graph isomorphism problem, as a stronger version of Monte Carlo algorithms.[1][2][3] Las Vegas algorithms can be used in situations where the number of possible solutions is relatively limited, and where verifying the correctness of a candidate solution is relatively easy while actually calculating the solution is complex.
- In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the correctness of the result; it gambles only 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.
- ↑ László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
- ↑ Leonid Levin, The Tale of One-way Functions, Problems of Information Transmission, vol. 39 (2003), 92-103.
- ↑ Dan Grundy, Concepts and Calculation in Cryptography, University of Kent, Ph.D. thesis, 2008