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)
“There is a certain class of people who prefer to say that their fathers came down in the world through their own follies than to boast that they rose in the world through their own industry and talents. It is the same shabby-genteel sentiment, the same vanity of birth which makes men prefer to believe that they are degenerated angels rather than elevated apes.”
—W. Winwood Reade (1838–1875)