Editing BPP (complexity) (section)

== 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 '''BPP'''<sub>path</sub>.<ref>{{cite web | url=https://complexityzoo.net/Complexity_Zoo:B#bpppath | title=Complexity Zoo:B - Complexity Zoo }}</ref> '''BPP'''<sub>path</sub> 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 (complexity)|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.