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

  • $\begingroup$ @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. $\endgroup$ Commented Oct 9, 2017 at 21:01
  • $\begingroup$ 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. $\endgroup$ Commented Oct 10, 2017 at 8:10

1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$ Commented Oct 10, 2017 at 9:13
  • $\begingroup$ 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. $\endgroup$ Commented Oct 10, 2017 at 15:47
  • $\begingroup$ And yes, the same argument shows more generally that $\mathrm{PP\subseteq ModPH\implies CH=P^{PP}=ModPH}$. $\endgroup$ Commented Oct 10, 2017 at 15:53
  • 6
    $\begingroup$ 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}$ $\endgroup$ Commented Oct 11, 2017 at 4:10
  • 1
    $\begingroup$ Yes, of course. Read the comments above. $\endgroup$ Commented Nov 29, 2017 at 22: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.