<p>We have
$$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$
thus by the assumption,
$$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$
as under the assumption, NP closed under complement. This implies $\mathrm{CH=NP}$.</p>

CC BY-SA 3.0
2017-10-10T09:13:28.297Z
Of course! More generally, the whole PH is low for $P^{PP}$, I can't believe I forgot that. What is the class $ModPH$? I can't find it in the zoo.
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2017-10-10T15:47:51.457Z
ModPH is the closure of P under the $\exists$, $\forall$, and $\mathrm{Mod}_m$ operators for all constants $m$. It’s sort of a common generalization of PH and the $\mathrm{Mod}_m\mathrm P$ classes.
Emil Jeřábek
CC BY-SA 3.0
2017-10-10T15:53:10.437Z
And yes, the same argument shows more generally that $\mathrm{PP\subseteq ModPH\implies CH=P^{PP}=ModPH}$.
Emil Jeřábek
CC BY-SA 3.0
2017-10-11T04:10:48.353Z
For the rest of us: the missing proofs above are mostly spelled out in J. Toran, Counting the number of solutions, MFCS'90. For the application above it's sufficient to show $PP^{BPP^A} \subseteq PP^A$ for all $A$ and $PP^{\oplus P} \subseteq P^{PP}$. Then $PP^{NP} \subseteq PP^{BPP^{\oplus P}} \subseteq PP^{\oplus P} \subseteq P^{PP}$
Ryan Williams
CC BY-SA 3.0
2017-11-29T19:58:21.780Z
@EmilJeřábek Searching for $ModPH$ got me here and it is not in zoo. So $ModPH$ contains the polynomial hierarchy?
Turbo
CC BY-SA 3.0
2017-11-29T22:02:26.823Z
Yes, of course. Read the comments above.
Emil Jeřábek
CC BY-SA 3.0
2017-10-10T07:58:08.917Z
2017-10-10T07:58:08.917Z
Emil Jeřábek
<p>Suppose $NP=PP$. Then a simple argument shows that $PH^{PP}=NP$. Can we go one step further and get $PP^{PP}=NP$? The simple argument is</p>

<p><strong>Theorem</strong> If $NP=PP$ then $PH^{PP}=NP$.</p>

<p><strong>Proof</strong> $PP$ is closed under complement (due to Gill), so $NP=coNP=PH$. Take any level of $PH^{PP}$: then $\Sigma_i^{P^{PP}}=\Sigma_i^{P^{NP}}=\Sigma_{i+1}^{P}=NP$. $\square$</p>

<p>One plausible-looking way to get to the desired consequence is by observing that in this world, the interactive proof protocol for the $\textsf{Permanent}$ has been derandomized and de-Merlinized to the point where one message to Arthur has perfect completeness and soundness (as $NP=P^{\#P}$ under the hypothesis). If you can exploit this fact and compute the Permanent in some class that's low for $PP$, such as $UP$ or $BQP$ or $SPP$, we're done. That would give us $NP=PP\implies PP=UP$ (for example), which would immediately give $PP^{PP}=PP^{UP}=PP=NP$.</p>

<p>(This came up in my thesis, where I investigate the hypothesis $QMA=PP$, and it also came up when trying to fix Scott Aaronson's broken theorem $PP\subset BQP_{/qpoly}\implies CH=PP=QMA$, Theorem 5 in Oracles are Subtle but not Malicious).</p>

CC BY-SA 3.0
2017-10-09T21:01:54.333Z
@EmilJeřábek You would think that $NP$ would be low for $PP$, since $NP\cap coNP$ is low for $NP$ and $NP\subseteq PP$, but no, that's not known. The classes $SPP$ and $BQP$ are known to be low for $PP$, and are incomparable as far as anybody knows. Then the class $\oplus P$ is something like low for $PP$, namely $PP^{\oplus P}\subseteq P^{PP}$, so if you gave a $\oplus P$-algorithm for the Permanent under this hypothesis, that gives us our desired collapse too.
Lieuwe Vinkhuijzen
CC BY-SA 3.0
2017-10-10T08:10:23.770Z
I slightly misremembered: NP is not known to be low for PP itself, but it is low for P^PP, which is good enough to get the conclusion.
Emil Jeřábek
<cc.complexity-theory><counting-complexity><conditional-results>
Does $NP=PP$ collapse the counting hierarchy?
Lieuwe Vinkhuijzen
# Does $NP=PP$ collapse the counting hierarchy?

(Asked by: username_0 on 2017-10-09)

Suppose $NP=PP$. Then a simple argument shows that $PH^{PP}=NP$. Can we go one step further and get $PP^{PP}=NP$? The simple argument is

**Theorem** If $NP=PP$ then $PH^{PP}=NP$.

**Proof** $PP$ is closed under complement (due to Gill), so $NP=coNP=PH$. Take any level of $PH^{PP}$: then $\Sigma\_i^{P^{PP}}=\Sigma\_i^{P^{NP}}=\Sigma\_{i+1}^{P}=NP$. $\square$

One plausible-looking way to get to the desired consequence is by observing that in this world, the interactive proof protocol for the $\textsf{Permanent}$ has been derandomized and de-Merlinized to the point where one message to Arthur has perfect completeness and soundness (as $NP=P^{\#P}$ under the hypothesis). If you can exploit this fact and compute the Permanent in some class that's low for $PP$, such as $UP$ or $BQP$ or $SPP$, we're done. That would give us $NP=PP\implies PP=UP$ (for example), which would immediately give $PP^{PP}=PP^{UP}=PP=NP$.

(This came up in my thesis, where I investigate the hypothesis $QMA=PP$, and it also came up when trying to fix Scott Aaronson's broken theorem $PP\subset BQP\_{/qpoly}\implies CH=PP=QMA$, Theorem 5 in Oracles are Subtle but not Malicious).

**Tags:** cc.complexity-theory, counting-complexity, conditional-results

> **Comments:**
> **username_0**: @EmilJeřábek You would think that $NP$ would be low for $PP$, since $NP\cap coNP$ is low for $NP$ and $NP\subseteq PP$, but no, that's not known. The classes $SPP$ and $BQP$ are known to be low for $PP$, and are incomparable as far as anybody knows. Then the class $\oplus P$ is something like low for $PP$, namely $PP^{\oplus P}\subseteq P^{PP}$, so if you gave a $\oplus P$-algorithm for the Permanent under this hypothesis, that gives us our desired collapse too.  
> **username_1**: I slightly misremembered: NP is not known to be low for PP itself, but it is low for P^PP, which is good enough to get the conclusion.  

---

## 1 answers

### Answer by username_1 on 2017-10-10. Score: 7 | Accepted answer

We have
$$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$
thus by the assumption,
$$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$
as under the assumption, NP closed under complement. This implies $\mathrm{CH=NP}$.

> **Comments:**
> **username_0**: Of course! More generally, the whole PH is low for $P^{PP}$, I can't believe I forgot that. What is the class $ModPH$? I can't find it in the zoo.  
> **username_1**: ModPH is the closure of P under the $\exists$, $\forall$, and $\mathrm{Mod}_m$ operators for all constants $m$. It’s sort of a common generalization of PH and the $\mathrm{Mod}_m\mathrm P$ classes.  
> **username_1**: And yes, the same argument shows more generally that $\mathrm{PP\subseteq ModPH\implies CH=P^{PP}=ModPH}$.  
> **username_2**: For the rest of us: the missing proofs above are mostly spelled out in J. Toran, Counting the number of solutions, MFCS'90. For the application above it's sufficient to show $PP^{BPP^A} \subseteq PP^A$ for all $A$ and $PP^{\oplus P} \subseteq P^{PP}$. Then $PP^{NP} \subseteq PP^{BPP^{\oplus P}} \subseteq PP^{\oplus P} \subseteq P^{PP}$  
> **username_3**: @EmilJeřábek Searching for $ModPH$ got me here and it is not in zoo. So $ModPH$ contains the polynomial hierarchy?  
> **username_1**: Yes, of course. Read the comments above.  

---

