# Does $NP=PP$ collapse the counting hierarchy?

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

• @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 Oct 9 '17 at 21:01
• 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 Oct 10 '17 at 8:10

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}$.

• 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 Oct 10 '17 at 9:13
• 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 Oct 10 '17 at 15:47
• And yes, the same argument shows more generally that $\mathrm{PP\subseteq ModPH\implies CH=P^{PP}=ModPH}$. – Emil Jeřábek Oct 10 '17 at 15:53
• 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 Oct 11 '17 at 4:10
• Yes, of course. Read the comments above. – Emil Jeřábek Nov 29 '17 at 22:02