Probabilistic Turing machine: Difference between revisions

Revision as of 00:54, 11 December 2016

Revision as of 03:46, 6 March 2017

Line 7:

As a consequence, a probabilistic Turing machine can (unlike a deterministic Turing Machine) have [[stochastic]] results; on a given input and instruction state machine, it may have different run times, or it may not halt at all; further, it may accept an input in one execution and reject the same input in another execution.

Therefore, 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]], Coco-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]], Coco-RL, [[BPL (complexity)|BPL]], and [[ZPL (complexity)|ZPL]] complexity classes are obtained. By enforcing both restrictions, [[Randomized Logarithmic-space Polynomial-time|RLP]], Coco-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.