Editing Complexity class (section)

====Important complexity classes====
[[File:Randomized Complexity Classes.svg|thumb|The relationships between the fundamental probabilistic complexity classes. BQP is a probabilistic [[Quantum complexity theory|quantum complexity]] class and is described in the quantum computing section.]]

The fundamental randomized time complexity classes are '''[[ZPP (complexity)|ZPP]]''', '''[[RP (complexity)|RP]]''', '''[[co-RP]]''', '''[[BPP (complexity)|BPP]]''', and '''[[PP (complexity)|PP]]'''.

The strictest class is '''[[ZPP (complexity)|ZPP]]''' (zero-error probabilistic polynomial time), the class of problems solvable in polynomial time by a probabilistic Turing machine with error probability 0. Intuitively, this is the strictest class of probabilistic problems because it demands ''no error whatsoever''. 

A slightly looser class is '''[[RP (complexity)|RP]]''' (randomized polynomial time), which maintains no error for strings not in the language but allows bounded error for strings in the language. More formally, a language is in '''RP''' if there is a probabilistic polynomial-time Turing machine <math>M</math> such that if a string is not in the language then <math>M</math> always rejects and if a string is in the language then <math>M</math> accepts with a probability at least 1/2. The class '''[[co-RP]]''' is similarly defined except the roles are flipped: error is not allowed for strings in the language but is allowed for strings not in the language. Taken together, the classes '''RP''' and '''co-RP''' encompass all of the problems that can be solved by probabilistic Turing machines with [[one-sided error]]. 

Loosening the error requirements further to allow for [[two-sided error]] yields the class '''[[BPP (complexity)|BPP]]''' (bounded-error probabilistic polynomial time), the class of problems solvable in polynomial time by a probabilistic Turing machine with error probability less than 1/3 (for both strings in the language and not in the language). '''BPP''' is the most practically relevant of the probabilistic complexity classes—problems in '''BPP''' have efficient [[randomized algorithm]]s that can be run quickly on real computers. '''BPP''' is also at the center of the important unsolved problem in computer science over whether '''[[BPP (complexity)#Problems|P=BPP]]''', which if true would mean that randomness does not increase the computational power of computers, i.e. any probabilistic Turing machine could be simulated by a deterministic Turing machine with at most polynomial slowdown. 

The broadest class of efficiently-solvable probabilistic problems is '''[[PP (complexity)|PP]]''' (probabilistic polynomial time), the set of languages solvable by a probabilistic Turing machine in polynomial time with an error probability of less than 1/2 for all strings.

'''ZPP''', '''RP''' and '''co-RP''' are all subsets of '''BPP''', which in turn is a subset of '''PP'''. The reason for this is intuitive: the classes allowing zero error and only one-sided error are all contained within the class that allows two-sided error, and '''PP''' simply relaxes the error probability of '''BPP'''. '''ZPP''' relates to '''RP''' and '''co-RP''' in the following way: <math>\textsf{ZPP}=\textsf{RP}\cap\textsf{co-RP}</math>. That is, '''ZPP''' consists exactly of those problems that are in both '''RP''' and '''co-RP'''. Intuitively, this follows from the fact that '''RP''' and '''co-RP''' allow only one-sided error: '''co-RP''' does not allow error for strings in the language and '''RP''' does not allow error for strings not in the language. Hence, if a problem is in both '''RP''' and '''co-RP''', then there must be no error for strings both in ''and'' not in the language (i.e. no error whatsoever), which is exactly the definition of '''ZPP'''. 

Important randomized space complexity classes include '''[[BPL (complexity)|BPL]]''', '''[[RL (complexity)|RL]]''', and '''[[Randomized Logarithmic-space Polynomial-time|RLP]]'''.