Probabilistic Turing machine: Difference between revisions

Revision as of 09:56, 2 April 2020

Revision as of 10:20, 2 April 2020

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 probailityprobability 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 [[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.

One of the central questions of complexity theory is whether randomness adds power; that is, is there a problem that can be solved in polynomial time by a probabilistic Turing machine but not a deterministic Turing machine? Or can deterministic Turing machines efficiently simulate all probabilistic Turing machines with at most a polynomial slowdown? It is currentlyknown widelythat believed'''P''' by<math>\subseteq</math> researchers{{Who|date=November'''BPP''', 2010}}since thata thedeterministic latterTuring machine is thejust a special case of a probabilistic Turing machine. However, whichit wouldis implyuncertain whether (but widely suspected that) '''BPP''' <math>\subseteq</math> '''P''', =implying that '''BPP''' = '''P'''. The same question for log space instead of polynomial time (does '''L''' = '''BPLP'''?) is even more widely believed to be true. On the other hand, the power randomness gives to interactive proof systems, as well as the simple algorithms it creates for difficult problems such as polynomial-time primality testing and log-space graph connectedness testing, suggests that randomness may add power.

==See also==