Las Vegas algorithm
|
|
In computing, a Las Vegas algorithm is a randomized algorithm which is correct; that is, it always produces the correct result. Thus, the random bits used only influence the resources used by the algorithm. A simple example is randomized quicksort, where the pivot is chosen randomly, but the result is always sorted. An alternative definition of a Las Vegas algorithm includes the restriction that the average-case running-time must be finite.
The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP.
Compare to the Monte Carlo method where the resources used are constant, but the random bits influence if the result is correct.