$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$

Question

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

Answer 1

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