Probabilistic Turing machine: Difference between revisions

Revision as of 09:26, 2 April 2020

Revision as of 09:37, 2 April 2020

Line 27:

==Complexity classes==

{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}

TheAs 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. Various polynomial-time randomized [[computational complexity theory|complexity classes]] that result from different definitions of acceptance include [[RP (complexity)|RP]], co-RP, [[Bounded-error probabilistic polynomial|BPP]] and [[ZPP (complexity)|ZPP]]. If the machine is restricted to logarithmic space instead of polynomial time, the analogous [[RL (complexity)|RL]], co-RL, [[BPL (complexity)|BPL]], and [[ZPL (complexity)|ZPL]] complexity classes are obtained. By enforcing both restrictions, [[Randomized Logarithmic-space Polynomial-time|RLP]], co-RLP, [[BPLP]], and [[ZPLP]] are yielded.

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.