Complexity Class
The complexity class of decision problems that have Las Vegas algorithms with expected polynomial runtime is ZPP.
It turns out that
which is intimately connected with the way Las Vegas algorithms are sometimes constructed. Namely the class 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: a few steps of each, 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.
Read more about this topic: Las Vegas Algorithm
Famous quotes containing the words complexity and/or class:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“You must drop all your democracy. You must not believe in “the people.” One class is no better than another. It must be a case of Wisdom, or Truth. Let the working classes be working classes. That is the truth. There must be an aristocracy of people who have wisdom, and there must be a Ruler: a Kaiser: no Presidents and democracies.”
—D.H. (David Herbert)