<ol>
<li>Unknown. There is an oracle $A$ s.t. $\bigoplus\mathsf{P}^A \not\subseteq \mathsf{PP}^A$. </li>
<li>There is an oracle $A$ s.t. $\mathsf{NP}^{\mathsf{NP}^A} \not\subseteq \mathsf{PP}^A$.</li>
<li>As far as I know no smaller class than $\mathsf{PP}$ is known to satisfy the inclusion.</li>
</ol>

CC BY-SA 3.0
2017-12-19T13:41:19.687Z
I meant smallest known class.
Turbo
CC BY-SA 3.0
2017-12-19T11:33:32.520Z
2017-12-19T13:56:27.417Z
2017-12-19T13:56:27.417Z
Kristoffer Arnsfelt Hansen
<p>Concerning 3, I believe $\mathrm{PP\subseteq\oplus P^{C_=P}}$, as there are at least $a$ numbers $x&lt;2^n$ satisfying $P(x)$ if and only if the number of $y&lt;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]}}$.))</p>

CC BY-SA 3.0
2017-12-19T14:07:14.190Z
You are right, of course.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-19T14:32:15.050Z
@EmilJerabek Just an unrelated query. Can $(Mod_aP)^{Mod_bP}$ be contained in $Mod_aP$ or ${Mod_bP}$ where $a,b$ are coprime?
Turbo
CC BY-SA 3.0
2017-12-19T15:13:45.940Z
That’s highly unlikely.
Emil Jeřábek
CC BY-SA 3.0
2017-12-19T17:05:01.570Z
And there are oracles relative to which they are not.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-19T19:17:47.610Z
What is the smallest class with $(Mod_aP)^{Mod_bP}$?
Turbo
CC BY-SA 3.0
2017-12-20T07:39:24.597Z
@EmilJeřábek actually I tried parsing your answer. I feel I miss something. How do you use $C_=P$ here and why is there only one such $y$? It will help me a bit more.
Turbo
CC BY-SA 3.0
2017-12-20T08:29:56.317Z
$y$, if it exists, is the $a$th number satisfying $P$. This defines it uniquely. The predicate $|\{x\le y:P(x)\}|=a$ is in $C_=P$.
Emil Jeřábek
CC BY-SA 3.0
2017-12-25T13:15:49.113Z
@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?
Turbo
CC BY-SA 3.0
2017-12-25T13:32:52.983Z
Also is $PromiseUP^X\subseteq\oplus P^X$ for any oracle?
Turbo
CC BY-SA 3.0
2017-12-29T16:07:36.030Z
I don’t know why I wrote promiseUP, it’s just plain $\mathrm{UP^{C_=P}}$. It’s still the same argument: we guess $y$ and verify it using the $\mathrm{C_=P}$ oracle.
Emil Jeřábek
CC BY-SA 4.0
2023-10-06T23:34:00.647Z
@EmilJeřábek Is there any consequence if $P^{GapP+}$ is in $\oplus P^{C_{=}P}$ or $P^{C_=P}$?
Turbo
CC BY-SA 4.0
2023-10-07T07:01:40.460Z
I don’t know what $\mathrm{P^{GapP+}}$ is. But $\mathrm{P^{GapP}=P^{PP}}$, while $\mathrm{\oplus P^{\oplus P^\mathit X}=\oplus P}^X$, thus it holds that $\mathrm{P^{GapP}\subseteq\oplus P^{GapP}\subseteq\oplus P^{C_=P}}$.
Emil Jeřábek
CC BY-SA 3.0
2017-12-19T13:57:02.640Z
2017-12-29T16:09:42.043Z
2017-12-29T16:09:42.043Z
Emil Jeřábek
<p>We know $\oplus P^{\oplus P}=\oplus P$, $PP^{\oplus P}\subseteq P^{PP}$ and $NP\subseteq PP$.</p>

<ol>
<li><p>Is $\oplus P^{PP}=PP$?</p></li>
<li><p>Why is it difficult to show $NP^{NP}\subseteq PP$?</p></li>
<li><p>What is the smallest known class $\mathcal C$ such that $PP\subseteq \oplus P^\mathcal C$ holds? Is there any class smaller than $PP$?</p></li>
</ol>

<cc.complexity-theory><complexity-classes>
On $NP$, $\oplus P$ and $PP$?
Turbo
# On $NP$, $\oplus P$ and $PP$?

(Asked by: username_0 on 2017-12-19)

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

**Tags:** cc.complexity-theory, complexity-classes


---

## 2 answers

### Answer by username_1 on 2017-12-19. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: I meant smallest known class.  

---

### Answer by username_2 on 2017-12-19. Score: 5

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

> **Comments:**
> **username_1**: You are right, of course.  
> **username_0**: @EmilJerabek Just an unrelated query. Can $(Mod_aP)^{Mod_bP}$ be contained in $Mod_aP$ or ${Mod_bP}$ where $a,b$ are coprime?  
> **username_2**: That’s highly unlikely.  
> **username_1**: And there are oracles relative to which they are not.  
> **username_0**: What is the smallest class with $(Mod_aP)^{Mod_bP}$?  
> **username_0**: @EmilJeřábek actually I tried parsing your answer. I feel I miss something. How do you use $C_=P$ here and why is there only one such $y$? It will help me a bit more.  
> **username_2**: $y$, if it exists, is the $a$th number satisfying $P$. This defines it uniquely. The predicate $|\{x\le y:P(x)\}|=a$ is in $C_=P$.  
> **username_0**: @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?  
> **username_0**: Also is $PromiseUP^X\subseteq\oplus P^X$ for any oracle?  
> **username_2**: I don’t know why I wrote promiseUP, it’s just plain $\mathrm{UP^{C_=P}}$. It’s still the same argument: we guess $y$ and verify it using the $\mathrm{C_=P}$ oracle.  
> **username_0**: @EmilJeřábek Is there any consequence if $P^{GapP+}$ is in $\oplus P^{C_{=}P}$ or $P^{C_=P}$?  
> **username_2**: I don’t know what $\mathrm{P^{GapP+}}$ is. But $\mathrm{P^{GapP}=P^{PP}}$, while $\mathrm{\oplus P^{\oplus P^\mathit X}=\oplus P}^X$, thus it holds that $\mathrm{P^{GapP}\subseteq\oplus P^{GapP}\subseteq\oplus P^{C_=P}}$.  

---

