11
$\begingroup$

Is $\mathsf{NP^{PP}} = \mathsf{P^{PP}}$? Or, more generally, Is $\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}$?

$\endgroup$
6
$\begingroup$

These are interesting open problems. Your second question effects a Karp-Lipton collapse.

Note that Toda's theorem gives you $NP\subseteq P^{PP}$, but that does not suffice for our purposes. We want to know whether $NP^{PP}\subseteq P^{PP}$, which makes this a funny question in my opninion.

1: Note that $NP^{PP}=NP^{\#P}$ and $P^{PP}=P^{\#P}$, so your first question has already been asked and answered here. Your are asking whether the polynomial hierarchy collapses relative to a $PP$ oracle (or equivalently relative to a $\#P$ oracle). According to this answer, that is an open question. If $P^{PP}=NP^{PP}$ then clearly the hierarchy does collapse relative to that oracle.

2: I think it is an open problem, and would be answered if we know whether the polynomial hierarchy collapses relative to a $PP$ oracle. Because, note that you get a Karp-Lipton collapse:

$$NP^{PP}\subset P^{PP}_{/poly} \text{ implies }{\Sigma_2^P}^{PP}={\Pi_2^P}^{PP}$$ Here I have only used the fact that the Karp-Lipton theorem relativizes. Whether you see this as evidence against the conjecture depends on whether you think the polynomial hierarchy collapses relative to $PP$, because if you think it collapses all the way down to $P$ relative to this oracle, then yes, $NP^{PP}=P^{PP}\subset P^{PP}_{/poly}$.

Going further, keep in mind that $$PP\subseteq P^{PP}\subseteq NP^{PP}\subseteq PP^{PP}=C_2^P,$$ and we do not have an oracle which separates $PP\subsetneq PP^{PP}$, so an oracle separation towards your first question, $P^{PP}\subsetneq NP^{PP}$, is more ambitious than that, and would be a nice result in its own right. Currently we do not even have an oracle relative to which $P^{PP}\subsetneq PSPACE$.

Personally I'd love to see the flipside: is $PP\subseteq NP_{/poly}$? We already know $PP$ is not contained in $P_{/n^k}$ for any fixed $k$. Can we show the same for $NP_{/n^k}$?

$\endgroup$

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.