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)


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

  • 5
    $\begingroup$ 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? $\endgroup$ Commented Jun 30, 2011 at 5:40
  • $\begingroup$ @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. – $\endgroup$ Commented Jun 30, 2011 at 6:24
  • 7
    $\begingroup$ 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. $\endgroup$ Commented Jun 30, 2011 at 7:38
  • 2
    $\begingroup$ @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! $\endgroup$ Commented Jul 1, 2011 at 0:13
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 1, 2011 at 6:49

1 Answer 1


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.

Also UPH=PH because you can make an existential unique by requiring the lexicographical least witness (using an extra universal quantifier to eliminate the others).

  • $\begingroup$ 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$. $\endgroup$ Commented Jul 2, 2011 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.