| Las Vegas Algorithm |
Article Index for Las Vegas |
Website Links For Las Vegas |
Information AboutLas Vegas Algorithm |
| CATEGORIES ABOUT LAS VEGAS ALGORITHM | |
| randomness | |
| algorithms | |
|
The Complexity Class of Decision Problem s 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. Las Vegas algorithms can be contrasted with Monte Carlo Algorithms , in which the resources used are bounded but the final result may not be 100% accurate, and Atlantic City Algorithm s, in which both computation time and the final result may be uncertain. |
|
|