Editing PP (complexity) (section)

{| class="wikitable" style="float:right; clear:right; text-align:center; margin-left:1em;"
|-
!colspan="3"| PP algorithm
|-
! {{diagonal split header|Correct<br />answer|Answer<div style{{=}}"padding-left:4em;">produced</div>}}
! {{yes}}
! {{no}}
|-
! {{yes}}
| > 1/2
| < 1/2
|-
! {{no}}
| < 1/2
| > 1/2
|}
{{short description|Class of problems in computer science}}
[[File:Randomised Complexity Classes 2.svg|alt=Diagram of randomised complexity classes|thumb|upright=1.25|PP in relation to other probabilistic complexity classes ([[ZPP (complexity)|ZPP]], [[RP (complexity)|RP]], co-RP, [[BPP (complexity)|BPP]], [[BQP]]), which generalise [[P (complexity)|P]] within [[PSPACE]]. It is unknown if any of these inclusions are strict.]]

In [[Computational complexity theory|complexity theory]], '''PP''', or '''PPT''' is the class of [[decision problem]]s solvable by a [[probabilistic Turing machine]] in [[polynomial time]], with an error probability of less than 1/2 for all instances. The abbreviation '''PP''' refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.<ref name=gill>{{Cite journal | doi=10.1137/0206049|title = Computational Complexity of Probabilistic Turing Machines| journal=SIAM Journal on Computing| volume=6| issue=4| pages=675–695|year = 1977|last1 = Gill|first1 = John}}</ref>

If a decision problem is in '''PP''', then there is an algorithm running in polynomial time that is allowed to make random decisions, such that it returns the correct answer with chance higher than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial-time algorithm a sufficient (but bounded) number of times.

Turing machines that are polynomially-bound and probabilistic are characterized as '''PPT''', which stands for probabilistic polynomial-time machines.<ref>{{cite book|last1=Lindell|first1=Yehuda |last2=Katz|first2=Jonathan|date=2015|title=Introduction to Modern Cryptography|publisher=Chapman and Hall/CRC|isbn=978-1-4665-7027-6|language=en|edition=2|page=46}}</ref> This characterization of Turing machines does not require a bounded error probability. Hence, '''PP''' is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2.

An alternative characterization of '''PP''' is the set of problems that can be solved by a [[nondeterministic Turing machine]] in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name ''Majority-P''.<ref>Lance Fortnow. Computational Complexity: Wednesday, September 4, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html</ref>