In literature, the biggest class I have seen proven to be in $PP$ is $NP$ (and $coNP$ of course as $PP$ is closed under complementation).
However, if we use the following results :
- $PP^{RP} = PP$ (in fact $PP^{BQP} = PP$)
- There exists a RP-reduction from $SAT$ to $USAT$
Where $USAT$ is the promise class of boolean formulae such that
- if $F \in USAT$ then $F$ has a unique solution.
- if $F \not \in USAT$ then $F$ is not satisfiable.
It seems quite straightforward to prove that $\Pi_2^P \subseteq PP$ (hence $\Sigma_2^P \subseteq PP$).
Construction: Let $\mathcal{M}\ $ be the following $PP^{RP}$ Turing Machine :
- Input: $\forall x_1, \dots, x_m, \exists y_1, \dots y_n, F$
Computation:
Choose uniformely $x_1, \dots, x_m$. We obtain then an existential formula. Use the Valiant-Vazirani theorem to obtain an USAT formula $\exists! z_1, \cdots z_o G$. We choose uniformly $z_1, \dots, z_o$, and if $G$ is satisfied, accept, otherwise, reject with probability $\frac{1}{2}$.
Modify the previous TM by adding $2^n-1$ rejecting paths. (I know I'm going a bit fast, but we can manage that by adjusting rejecting probabilities after having tested G)
Validity:
- if $\forall \dots \exists \dots F$ is true, then $\mathcal{M}\ $ has $2^n$ accepting paths + $2^{n-1}$ rejecting paths + an equal number of accepting and rejecting paths, and then $\mathcal{M}\ $ accepts.
- if $\forall \dots \exists \dots F$ is false, then $\mathcal{M}\ $ has less than $2^n$ accepting paths + $2^n-1$ rejecting maths + more rejecting paths than accepting paths. then $\mathcal{M}\ $ rejects.
Moreover, if we extend Valiant-Vazirani theorem to $RP$-reduce $PH$ to $UPH$ (alternation of forall and unique existentials), then by modifying a bit previous construction we would prove that $PH \subseteq PP$.
Is the previous construction correct ?
Is there any known litterature around $UPH$ ? (It may not be called $UPH$)
