<p>These are interesting open problems. Your second question effects a Karp-Lipton collapse.</p>

<p>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.</p>

<p>1: Note that $NP^{PP}=NP^{\#P}$ and $P^{PP}=P^{\#P}$, so your first question has already been asked and answered <a href="https://cstheory.stackexchange.com/q/2559/35749">here</a>. Your are asking whether the polynomial hierarchy collapses relative to a $PP$ oracle (or equivalently relative to a $\#P$ oracle). According to <a href="https://cstheory.stackexchange.com/a/4691/35749">this answer</a>, that is an open question. If $P^{PP}=NP^{PP}$ then clearly the hierarchy does collapse relative to that oracle.</p>

<p>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:</p>

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

<p>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$.</p>

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

CC BY-SA 3.0
2017-07-17T19:42:13.810Z
2017-07-19T11:04:58.787Z
2017-07-19T11:04:58.787Z
Lieuwe Vinkhuijzen
<p>Is $\mathsf{NP^{PP}} = \mathsf{P^{PP}}$? Or, more generally, Is $\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}$?</p>

<complexity-classes>
$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
Ilya Volkovich
# $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$

(Asked by: username_0 on 2016-09-29)

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

**Tags:** complexity-classes

---

## 1 answers

### Answer by username_1 on 2017-07-17. Score: 6

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](https://cstheory.stackexchange.com/q/2559/35749). Your are asking whether the polynomial hierarchy collapses relative to a $PP$ oracle (or equivalently relative to a $\#P$ oracle). According to [this answer](https://cstheory.stackexchange.com/a/4691/35749), 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}$?


---

