Content deleted Content added
→Complexity classes: expanded and typo fix |
→Complexity classes: made boldface formatting uniform across section |
||
Line 29:
As a result of the error introduced by utilizing probabilistic coin tosses, the notion of acceptance of a string by a probabilistic Turing machine can be defined in different ways. One such notion that includes several important complexity classes is allowing for an error probability of 1/3. For instance, the complexity class '''[[Bounded-error probabilistic polynomial|BPP]]''' is defined as the class of languages recognized by a probabilistic Turing machine in [[polynomial time]] with an error probability of 1/3. Another class defined using this notion of acceptance is '''[[BPL (complexity)|BPL]]''', which is the same as '''BPP''' but places the additional restriction that languages must be solvable in [[Logarithmic growth|logarithmic]] [[space complexity|space]].
[[Complexity class]]es arising from other definitions of acceptance include '''[[RP (complexity)|RP]]''' and '''co-RP''' (error probability of 1/2), and '''[[ZPP (complexity)|ZPP]]''' (error probability of 0). If the machine is restricted to logarithmic space instead of polynomial time, the analogous '''[[RL (complexity)|RL]]''', '''co-RL''', and '''[[ZPL (complexity)|ZPL]]''' complexity classes are obtained. By enforcing both restrictions, '''[[Randomized Logarithmic-space Polynomial-time|RLP]]''', '''co-RLP''', '''[[BPLP]]''', and
Probabilistic computation is also critical for the definition of most classes of [[interactive proof system]]s, in which the verifier machine depends on randomness to avoid being predicted and tricked by the all-powerful prover machine. For example, the class '''[[IP (complexity)|IP]]''' equals '''[[PSPACE]]''', but if randomness is removed from the verifier, we are left with only '''[[NP (complexity)|NP]]''', which is not known but widely believed to be a considerably smaller class.
| |||