<p>Your proof must be wrong. All your techniques (including VV) relativize and Beigel has an <a href="http://www.springerlink.com/content/u57567564x383634/" rel="noreferrer">oracle</a> where $P^{NP}$ is not contained in $PP$. I'm guessing you aren't using VV properly.</p>

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

CC BY-SA 3.0
2011-07-02T01:02:36.317Z
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$.
Ludovic Patey
CC BY-SA 3.0
2011-07-01T14:42:03.607Z
2011-07-01T14:42:03.607Z
Lance Fortnow
<p>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).</p>

<p>However, if we use the following results :</p>

<ul>
<li>$PP^{RP} = PP$  (in fact $PP^{BQP} = PP$)</li>
<li>There exists a RP-reduction from $SAT$ to $USAT$</li>
</ul>

<p>Where $USAT$ is the promise class of boolean formulae such that</p>

<ul>
<li>if $F \in USAT$ then $F$ has a unique solution.</li>
<li>if $F \not \in USAT$ then $F$ is not satisfiable.</li>
</ul>

<p>It seems quite straightforward to prove that $\Pi_2^P \subseteq PP$ (hence $\Sigma_2^P \subseteq PP$).</p>

<blockquote>
  <p><strong>Construction:</strong>
  Let $\mathcal{M}\ $ be the following $PP^{RP}$  Turing Machine :</p>
  
  <ul>
  <li>Input: $\forall x_1, \dots, x_m, \exists y_1, \dots y_n, F$</li>
  <li><p>Computation: </p>
  
  <p>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}$.</p>
  
  <p>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)</p></li>
  </ul>
  
  <p><strong>Validity:</strong></p>
  
  <ul>
  <li>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.</li>
  <li>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.</li>
  </ul>
</blockquote>

<p>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$.</p>

<blockquote>
  <p>Is the previous construction correct ?</p>
  
  <p>Is there any known litterature around $UPH$ ? (It may not be called $UPH$)</p>
</blockquote>

CC BY-SA 3.0
2011-06-30T05:40:20.643Z
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
CC BY-SA 3.0
2011-06-30T06:24:09.453Z
@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. –
Ludovic Patey
CC BY-SA 3.0
2011-06-30T07:38:18.677Z
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
CC BY-SA 3.0
2011-06-30T21:38:34.073Z
@Ryan: make this an answer ?
Suresh Venkat
CC BY-SA 3.0
2011-07-01T00:13:47.453Z
@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
CC BY-SA 3.0
2011-07-01T00:49:56.453Z
@Ryan. Thank you. I will go in more details.
Ludovic Patey
CC BY-SA 3.0
2011-07-01T06:49:59.760Z
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. http://arxiv.org/abs/cs/9907033 and http://dx.doi.org/10.1007/3-540-56503-5_47.
Joshua Grochow
<cc.complexity-theory><complexity-classes>
$\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$
Ludovic Patey
# $\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$

(Asked by: username_0 on 2011-06-30)

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

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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. –  
> **username_1**: 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.  
> **username_2**: @Ryan: make this an answer ?  
> **username_1**: @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!  
> **username_0**: @Ryan. Thank you. I will go in more details.  
> **username_3**: 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. http://arxiv.org/abs/cs/9907033 and http://dx.doi.org/10.1007/3-540-56503-5_47.  

---

## 1 answers

### Answer by username_4 on 2011-07-01. Score: 12 | Accepted answer

Your proof must be wrong. All your techniques (including VV) relativize and Beigel has an [oracle](http://www.springerlink.com/content/u57567564x383634/) 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).

> **Comments:**
> **username_0**: 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$.  

---

