Complexity Classes
The complexity class BPP describes decision problems that can be solved by polynomial-time Monte Carlo algorithms with a bounded probability of two-sided errors, and the complexity class RP describes problems that can be solved by a Monte Carlo algorithm with a bounded probability of one-sided error: if the correct answer is no, the algorithm always says so, but it may answer no incorrectly for some instances where the correct answer is yes. In contrast, the complexity class ZPP describes problems solvable by polynomial expected time Las Vegas algorithms. ZPP ⊂ RP ⊂ BPP, but it is not known whether any of these complexity classes is distinct from each other; that is, Monte Carlo algorithms may have more computational power than Las Vegas algorithms, but this has not been proven. Another complexity class, PP, describes decision problems with a polynomial-time Monte Carlo algorithm that is more accurate than flipping a coin but where the error probability cannot be bounded away from 1/2.
Read more about this topic: Monte Carlo Algorithm
Famous quotes containing the words complexity and/or classes:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)
“Solidity, caution, integrity, efficiency. Lack of imagination, hypocrisy. These qualities characterize the middle classes in every country, but in England they are national characteristics.”
—E.M. (Edward Morgan)