Content deleted Content added
changed to "In theoretical computer science" because probabilistic TM's are relevant to both computability and complexity theory |
merged two sentences into a paragraph |
||
Line 2:
{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}
{{turing}}
In [[theoretical computer science]], a '''probabilistic Turing machine''' is a [[non-deterministic Turing machine]] which chooses between the available transitions at each point according to some [[probability distribution]]. 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.
In the case of equal probabilities for the transitions, it can be defined as a deterministic [[Turing machine]] having an additional "write" instruction where the value of the write is [[uniform distribution (discrete)|uniformly distributed]] in the Turing Machine's alphabet (generally, an equal likelihood of writing a '1' or a '0' on to the tape.) Another common reformulation is simply a [[deterministic Turing machine]] with an added tape full of random bits called the ''random tape''.
▲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]], 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.
| |||