Probabilistic Turing machine: Difference between revisions

Revision as of 09:37, 2 April 2020

Revision as of 09:56, 2 April 2020

Line 27:

==Complexity classes==

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

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. VariousOne polynomial-timesuch randomizednotion [[computationalthat complexityincludes several important theory|complexity classes]] thatis resultallowing fromfor differentan error definitionsprobability of acceptance1/3. includeFor [[RPinstance, the (complexity)|RP]], co-RP,class '''[[Bounded-error probabilistic polynomial|BPP]]''' andis defined as the class of languages recognized by a probabilistic Turing machine in [[ZPPpolynomial (complexity)|ZPPtime]]. Ifwith thean machineerror isprobability restrictedof to1/3. logarithmicAnother spaceclass insteaddefined ofusing polynomialthis time,notion theof analogousacceptance [[RL (complexity)|RL]], co-RL,is '''[[BPL (complexity)|BPL]]''', andwhich [[ZPLis (complexity)|ZPL]]the complexitysame classesas are'''BPP''' obtained.but Byplaces enforcingthe bothadditional restrictions,restriction that languages must be solvable in [[Randomized Logarithmic-space Polynomial-timegrowth|RLPlogarithmic]], co-RLP, [[BPLP]],space and [[ZPLPcomplexity|space]]. are yielded.

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