Complexity Class of the Week: PP

Previous CCW

A language L is in PP if there is a nondeterministic polynomial-time Turing machine M such that x is in L if and only if M(x) has more accepting than rejecting paths.

PP stands for "Probabilistic Polynomial-time" from the original definition by Gill where one uses a probabilistic poly-time TM where x is in L if and only if the probability of M(x) accepting is greater than 1/2. "Probabilistic Polynomial-Time" would be a better name for PP's cousin class BPP or "Bounded-error Probabilistic Polynomial-Time". PP is not much use as a probabilistic class since it would take potentially an exponential number of trials to distinguish accepting from rejecting with reasonable confidence

A better name for PP would be Majority-P as given by the definition above. Because of historic reasons we are stuck with the name PP for now. Don't hold the bad name against the class. It still has a natural definition and some amazing properties.

PP has similar complexity to the function class #P as P^PP = P^#P, proved using the old stalwart, binary search. I have never found the paper that first proves this equivalence. Toda's Theorem shows the amazing hardness of PP by reducing the polynomial-time hierarchy to P^PP.

Valiant's proof that the permanent is #P-complete also gives a natural complete language for PP:

PERM = { (M,k) | The permanent of M is at least k}

NP is in PP by adding a larger number of dummy accepting paths. PP is clearly closed under complement so we have co-NP in PP. Beigel, Reingold and Spielman show that PP is closed under union, a far trickier proof than one would expect using the fact that rational functions approximate the sign function well. Fortnow and Reingold build on their techniques to show that PP is closed under truth-table reductions.

PP is the prototypical counting class, classes defined in terms of the number of accepting and rejecting paths. PP contains the counting class C₌P where x is in the language if the number of accepting paths equals the number of rejecting paths. On the other hand there are relativized worlds where ⊕P and PP are incomparable.

The limitations of PP come from what I call the Beigel all-purpose oracle. Beigel exhibits a relativized world where P^NP is not contained in PP. His proof works by showing that any polynomial whose sign is the ODDMAXBIT function must either have high-degree or very large coefficients.

PP has interesting relationships to other complexity classes. Vereshchagin shows that Merlin-Arthur games, the class MA, is contained in PP but gives a relativized world where AM is not in PP. Adleman, DeMarrais and Huang show that the quantum class BQP is contained in PP. Watrous shows that QMA, the quantum version of MA, is also contained in PP.

Fortnow and Rogers, building Lide Li's Ph.D. thesis, show that BQP is low for PP, i.e., PP^BQP = PP. Köbler, Schöning and Torán also using the work of Li show that graph isomorphism is also low for PP.

Allender shows that PP is not equal to uniform-TC⁰, constant-depth circuits with threshold gates. Can one show that PP is not equal to log-space? All one has to do is show that Toda's theorem can be extended to get any nonconstant level of the polynomial-time hierarchy to fall in P^PP.