8
$\begingroup$

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

$\endgroup$
  • $\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$ – Lieuwe Vinkhuijzen Oct 9 '17 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$ – Emil Jeřábek Oct 10 '17 at 8:10
7
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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