Editing Las Vegas algorithm (section)

== Complexity class ==
The [[complexity class]] of [[decision problem]]s that have Las Vegas algorithms with [[Expected value|expected]] polynomial runtime is [[Zero-error Probabilistic Polynomial time|ZPP]].

It turns out that
: <math>\textsf{ZPP} = \textsf{RP} \cap \textsf{co-RP}</math>

which is intimately connected with the way Las Vegas algorithms are sometimes constructed. Namely the class [[RP (complexity)|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: run each for a constant number of steps, 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.