Editing PP (complexity) (section)

==Complete problems and other properties==
Unlike '''BPP''', '''PP''' is a syntactic rather than semantic class. Any polynomial-time probabilistic machine recognizes some language in '''PP'''. In contrast, given a description of a polynomial-time probabilistic machine, it is undecidable in general to determine if it recognizes a language in '''BPP'''.

'''PP''' has natural complete problems, for example, '''MAJSAT'''.<ref name=gill/> '''MAJSAT''' is a decision problem in which one is given a Boolean formula F. The answer must be YES if more than half of all assignments ''x''<sub>1</sub>,&nbsp;''x''<sub>2</sub>,&nbsp;...,&nbsp;''x''<sub>''n''</sub> make F true and NO otherwise.

{{Anchor|complement}}

===Proof that PP is closed under complement===
Let ''L'' be a language in '''PP'''. Let <math>L^c</math> denote the complement of ''L''. By the definition of '''PP''' there is a polynomial-time probabilistic algorithm ''A'' with the property that 

:<math>x \in L \Rightarrow \Pr[A \text{ accepts } x] > \frac{1}{2} \quad \text{and} \quad x \not\in L \Rightarrow \Pr[A \text{ accepts } x] \le \frac{1}{2}.</math>

We claim that [[without loss of generality]], the latter inequality is always strict; the theorem can be deduced from this claim: let <math>A^c</math> denote the machine which is the same as ''A'' except that <math>A^c</math> accepts when ''A'' would reject, and vice versa. Then 

:<math>x \in L^c \Rightarrow \Pr[A^c \text{ accepts } x] > \frac{1}{2} \quad \text{and} \quad x \not\in L^c \Rightarrow \Pr[A^c \text{ accepts } x] <  \frac{1}{2},</math>

which implies that <math>L^c</math> is in '''PP'''.

Now we justify our without loss of generality assumption. Let <math>f(|x|)</math> be the polynomial upper bound on the running time of ''A'' on input ''x''. Thus ''A'' makes at most <math>f(|x|)</math> random coin flips during its execution. In particular the probability of acceptance is an integer multiple of <math>2^{-f(|x|)}</math> and we have:

:<math>x \in L \Rightarrow \Pr[A \text{ accepts } x] \ge \frac{1}{2} + \frac{1}{2^{f(|x|)}}.</math> 

Define a machine ''A''′ as follows: on input ''x'', ''A''′ runs ''A'' as a subroutine, and rejects if ''A'' would reject; otherwise, if ''A'' would accept, ''A''′ flips <math>f(|x|)+1</math> coins and rejects if they are all heads, and accepts otherwise. Then 

:<math>x \not\in L \Rightarrow \Pr[A' \text{ accepts } x] \le \frac{1}{2} \cdot \left (1- \frac{1}{2^{f(|x|)+1}} \right ) < \frac{1}{2}</math>
and
:<math> x \in L \Rightarrow \Pr[A' \text{ accepts } x] \ge \left (\frac{1}{2}+\frac{1}{2^{f(|x|)}} \right )\cdot \left ( 1-\frac{1}{2^{f(|x|)+1}} \right ) > \frac{1}{2}.</math>

This justifies the assumption (since ''A''′ is still a polynomial-time probabilistic algorithm) and completes the proof.

David Russo proved in his 1985 Ph.D. thesis<ref>{{cite thesis| title = Structural Properties of Complexity Classes| type = Ph.D Thesis| publisher=University of California, Santa Barbara | year = 1985 | author = David Russo}}</ref> that '''PP''' is closed under [[symmetric difference]]. It was an [[open problem]] for 14 years whether '''PP''' was closed under [[union (set theory)|union]] and [[Intersection (set theory)|intersection]]; this was settled in the affirmative by Beigel, Reingold, and Spielman.<ref>R. Beigel, N. Reingold, and D. A. Spielman, "[http://citeseer.ist.psu.edu/152946.html PP is closed under intersection]", ''Proceedings of ACM Symposium on Theory of Computing 1991'', pp. 1–9, 1991.</ref> Alternate proofs were later given by Li<ref>{{cite thesis| title = On the Counting Functions| type= Ph.D Thesis  | publisher=University of Chicago| year = 1993| author = Lide Li}}</ref> and Aaronson (see [[#PostBQP]] below).