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:
“Becoming responsible adults is no longer a matter of whether children hang up their pajamas or put dirty towels in the hamper, but whether they care about themselves and others—and whether they see everyday chores as related to how we treat this planet.”
—Eda Le Shan (20th century)
“... too much attention is paid to dress by those who have neither the excuse of ample means nor of social claims.... The injury done by this state of things to the morals and the manners of our lower classes is incalculable.”
—Mrs. H. O. Ward (1824–1899)