Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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? – Ryan Williams Jun 30 '11 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. – – Turingoid Jun 30 '11 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. – Ryan Williams Jun 30 '11 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! – Ryan Williams Jul 1 '11 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. and – Joshua Grochow Jul 1 '11 at 6:49
up vote 11 down vote accepted

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

share|cite|improve this answer
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$. – Turingoid Jul 2 '11 at 1:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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