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

$\endgroup$
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.
$\endgroup$
1
  • $\begingroup$ I meant smallest known class. $\endgroup$
    – Mr.
    Dec 19 '17 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]}}$.))

$\endgroup$
10
  • $\begingroup$ You are right, of course. $\endgroup$ Dec 19 '17 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$
    – Mr.
    Dec 19 '17 at 14:32
  • $\begingroup$ That’s highly unlikely. $\endgroup$ Dec 19 '17 at 15:13
  • $\begingroup$ And there are oracles relative to which they are not. $\endgroup$ Dec 19 '17 at 17:05
  • 1
    $\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$
    – Mr.
    Dec 25 '17 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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