# $\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$

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$)

• Valiant-Vazirani has some probability of failure -- i.e., it doesn't always produce a formula with a unique solution. Your analysis of the number of accepting computation paths should take into account the possible outcomes that the Valiant-Vazirani reduction produces, and their respective probabilities of occurring. Or is the idea that the RP oracle is somehow computing the Valiant-Vazirani reduction? Jun 30, 2011 at 5:40
• @Ryan Yes, my idea is to put the valiant-vazirani reduction as oracle. I'm not sure about wether we can make this reduction because RP is a class of decision problems whereas the random reduction is a function. We may need to prove that Valiant-Vazirani reduction function is self-reducible. – Jun 30, 2011 at 6:24
• Forgot to say: It is also known that $MA$ is contained in $PP$. See N. Vereshchagin. On the Power of PP. Proc. 7th IEEE Conference on Structure in Complexity Theory, 138--143, 1992. Jun 30, 2011 at 7:38
• @Suresh: I thought I'd give Monoid a chance to make his question/proof more detailed. I've noticed that when a questioner and answerer go back and forth, revising the question and revising the answer in stages, the end result may not be readable by third parties! Jul 1, 2011 at 0:13
• Not quite what you asked for, but people have looked at the $UP$ oracle hierarchy ($UP$, $UP^{UP}$, $UP^{UP^{UP}}$, etc) and also alternation of unambiguous existential and unambiguous universal quantifiers, and promise versions. See e.g. arxiv.org/abs/cs/9907033 and dx.doi.org/10.1007/3-540-56503-5_47. Jul 1, 2011 at 6:49

Your proof must be wrong. All your techniques (including VV) relativize and Beigel has an oracle where $P^{NP}$ is not contained in $PP$. I'm guessing you aren't using VV properly.
• So if I understand, as a consequence, let $O$ an oracle taking a SAT formula and transforming it into an USAT one, then there exist an oracle $A$ such that ${PP^O}^A \neq PP^A$. Jul 2, 2011 at 1:02