Editing Las Vegas algorithm (section)

{{Short description|Type of randomized algorithm}}
In [[computing]], a '''Las Vegas algorithm''' is a [[randomized algorithm]] that always gives [[Correctness (computer science)|correct]] results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the ''expected'' runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is [[Effective method|effective]]), but may output a [[Partial function#Bottom element|symbol not part of the solution space]] to indicate failure in finding a solution.<ref name="Galbraith201222">{{cite book|title=Mathematics of Public Key Cryptography|author=Steven D. Galbraith|publisher=Cambridge University Press|year=2012|isbn=978-1-107-01392-6|page=16}}</ref> The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex.

Systematic search methods for computationally hard problems, such as some variants of the [[Davis–Putnam algorithm]] for propositional satisfiability (SAT), also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms.<ref>Hoos, Holger H.. “On the Empirical Evaluation of Las Vegas Algorithms — Position Paper.” (1998).</ref>