Editing PP (complexity) (section)

==PP compared to other complexity classes==

'''PP''' includes '''BPP''', since probabilistic algorithms described in the definition of '''BPP''' form a subset of those in the definition of '''PP'''.

'''PP''' also includes '''[[NP (complexity class)|NP]]'''. To prove this, we show that the [[NP-complete]] [[Boolean satisfiability problem|satisfiability]] problem belongs to '''PP'''. Consider a probabilistic algorithm that, given a formula ''F''(''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;...,&nbsp;''x''<sub>''n''</sub>) chooses an assignment ''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;...,&nbsp;''x''<sub>''n''</sub> uniformly at random. Then, the algorithm checks if the assignment makes the formula ''F'' true. If yes, it outputs YES. Otherwise, it outputs YES with probability <math>\frac12 - \frac1{2^{n + 1}}</math> and NO with probability <math>\frac12 + \frac1{2^{n + 1}}</math>.

If the formula is unsatisfiable, the algorithm will always output YES with probability <math>\frac12 - \frac1{2^{n + 1}} < \frac12</math>. If there exists a satisfying assignment, it will output YES with probability at least
<math>\left(\frac12 - \frac1{2^{n + 1}}\right)\cdot \left(1 - \frac1{2^n}\right) + 1\cdot\frac1{2^n} = \frac12 + \frac1{2^{2n + 1}} > \frac12</math>
(exactly 1/2 if it picked an unsatisfying assignment and 1 if it picked a satisfying assignment, averaging to some number greater than 1/2). Thus, this algorithm puts satisfiability in '''PP'''. As '''SAT''' is NP-complete, and we can prefix any deterministic [[polynomial-time many-one reduction]] onto the '''PP''' algorithm, '''NP''' is included in '''PP'''. Because '''PP''' is closed under complement, it also includes '''co-NP'''.

Furthermore, '''PP''' includes '''[[Arthur–Merlin protocol|MA]]''',<ref>[http://lpcs.math.msu.su/~ver/papers/am-pp.ps N.K. Vereshchagin, "On the Power of PP"]</ref> which subsumes the previous two inclusions.

'''PP''' also includes '''[[BQP]]''', the class of decision problems solvable by efficient polynomial time [[quantum computer]]s. In fact, BQP is [[low (complexity)|low]] for '''PP''', meaning that a '''PP''' machine achieves no benefit from being able to solve '''BQP''' problems instantly. The class of polynomial time on quantum computers with [[postselection]], '''[[PostBQP]]''', is equal to '''PP'''<ref name="PostBQP = PP">{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=Proceedings of the Royal Society A|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546|arxiv=quant-ph/0412187|bibcode=2005RSPSA.461.3473A|s2cid=1770389 }}</ref> (see [[#PostBQP]] below).

Furthermore, '''PP''' includes '''[[QMA]]''', which subsumes inclusions of '''MA''' and '''BQP'''.

A polynomial time Turing machine with a PP [[oracle machine|oracle]] ('''P<sup>PP</sup>''') can solve all problems in  '''[[PH (complexity)|PH]]''', the entire [[polynomial hierarchy]]. This result was shown by [[Seinosuke Toda]] in 1989 and is known as [[Toda's theorem]]. This is evidence of how hard it is to solve problems in '''PP'''. The class [[Sharp-P|#P]] is in some sense about as hard, since '''P'''<sup>'''#P'''</sup> = '''P<sup>PP</sup>''' and therefore '''P'''<sup>'''#P'''</sup> includes '''PH''' as well.<ref>{{cite journal
 | last = Toda | first = Seinosuke | author-link = Seinosuke Toda
 | doi = 10.1137/0220053
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | mr = 1115655
 | pages = 865–877
 | title = PP is as hard as the polynomial-time hierarchy
 | volume = 20
 | year = 1991}}</ref>

'''PP''' strictly includes uniform '''[[TC0|TC<sup>0</sup>]]''', the class of constant-depth, unbounded-fan-in [[boolean circuit]]s with [[majority gate]]s that are uniform (generated by a polynomial-time algorithm).<ref>Allender 1996, as cited in Burtschick 1999</ref>

'''PP''' is included in '''[[PSPACE]]'''. This can be easily shown by exhibiting a polynomial-space algorithm for '''MAJSAT''', defined below; simply try all assignments and count the number of satisfying ones.

'''PP''' is not included in '''SIZE'''(n<sup>k</sup>) for any k, by [[Karp-Lipton theorem#Application to circuit lower bounds – Kannan's theorem|Kannan's theorem]].