Content deleted Content added
added a description section |
moved "unsolved" template |
||
Line 1:
{{no sources|date=February 2018}}
{{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.
Line 12 ⟶ 11:
==Complexity classes==
▲{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}
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.
| |||