4
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$
  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.
Improve this answer
$\endgroup$
1
  • $\begingroup$ I meant smallest known class. $\endgroup$
    – Turbo
    Commented Dec 19, 2017 at 13:41
5
$\begingroup$

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

Improve this answer
$\endgroup$
12
  • $\begingroup$ You are right, of course. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Dec 19, 2017 at 14:07
  • $\begingroup$ @EmilJerabek Just an unrelated query. Can $(Mod_aP)^{Mod_bP}$ be contained in $Mod_aP$ or ${Mod_bP}$ where $a,b$ are coprime? $\endgroup$
    – Turbo
    Commented Dec 19, 2017 at 14:32
  • $\begingroup$ That’s highly unlikely. $\endgroup$
    – Emil Jeřábek
    Commented Dec 19, 2017 at 15:13
  • $\begingroup$ And there are oracles relative to which they are not. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Dec 19, 2017 at 17:05
  • 2
    $\begingroup$ @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? $\endgroup$
    – Turbo
    Commented Dec 25, 2017 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.