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:
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“The most powerful lessons about ethics and morality do not come from school discussions or classes in character building. They come from family life where people treat one another with respect, consideration, and love.”
—Neil Kurshan (20th century)