Related Classes
If the access to randomness is removed from the definition of BPP, we get the complexity class P. In the definition of the class, if we replace the ordinary Turing machine with a quantum computer, we get the class BQP.
Adding postselection to BPP, or allowing computation paths to have different lengths, gives the class BPPpath. BPPpath is known to contain NP, and it is contained in its quantum counterpart PostBQP.
A Monte Carlo algorithm is a randomized algorithm which is likely to be correct. Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time. This is compared to a Las Vegas algorithm which is a randomized algorithm which either outputs the correct answer, or outputs "fail" with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class ZPP. Alternatively, ZPP contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time, but with very low probability.
Read more about this topic: BPP (complexity)
Famous quotes containing the words related and/or classes:
“Just as a new scientific discovery manifests something that was already latent in the order of nature, and at the same time is logically related to the total structure of the existing science, so the new poem manifests something that was already latent in the order of words.”
—Northrop Frye (b. 1912)
“Of all classes the rich are the most noticed and the least studied.”
—John Kenneth Galbraith (b. 1908)