# On $NP$, $\oplus P$ and $PP$?

We know $\oplus P^{\oplus P}=\oplus P$, $PP^{\oplus P}\subseteq P^{PP}$ and $NP\subseteq PP$.

1. Is $\oplus P^{PP}=PP$?

2. Why is it difficult to show $NP^{NP}\subseteq PP$?

3. What is the smallest known class $\mathcal C$ such that $PP\subseteq \oplus P^\mathcal C$ holds? Is there any class smaller than $PP$?

## 2 Answers

1. Unknown. There is an oracle $A$ s.t. $\bigoplus\mathsf{P}^A \not\subseteq \mathsf{PP}^A$.
2. There is an oracle $A$ s.t. $\mathsf{NP}^{\mathsf{NP}^A} \not\subseteq \mathsf{PP}^A$.
3. As far as I know no smaller class than $\mathsf{PP}$ is known to satisfy the inclusion.
• I meant smallest known class.
– Mr.
Dec 19 '17 at 13:41

Concerning 3, I believe $\mathrm{PP\subseteq\oplus P^{C_=P}}$, as there are at least $a$ numbers $x<2^n$ satisfying $P(x)$ if and only if the number of $y<2^n$ such that $P(y)\land|\{x\le y:P(x)\}|=a$ is odd. (Note that there is always at most one such $y$. That is, the argument actually shows $\mathrm{PP\subseteq UP^{C_=P}}$. (In fact, it even shows $\mathrm{UP^{PP}=UP^{C_=P}=UP^{C_=P[1]}}$.))

• You are right, of course. Dec 19 '17 at 14:07
• @EmilJerabek Just an unrelated query. Can $(Mod_aP)^{Mod_bP}$ be contained in $Mod_aP$ or ${Mod_bP}$ where $a,b$ are coprime?
– Mr.
Dec 19 '17 at 14:32
• That’s highly unlikely. Dec 19 '17 at 15:13
• And there are oracles relative to which they are not. Dec 19 '17 at 17:05
• @EmilJeřábek $|\{x\leq y:P(x)\}|=a$ is in $C_=P$ is a middle point argument. There is at most one such $y$ because $a$ is fixed (So we either have $1$ or $0$). We fix $a=\mbox{half number of paths}$ and query once. Correct? The querying part with $PromiseUP$ is not clear to me. Do we non-deterministically guess something and make the query?
– Mr.
Dec 25 '17 at 13:15