Complexity zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dtime states $DTIME(f(n))$ with $PP$ oracle is not in $P/Poly$ if $f(n)$ is superpolynomial.

We know $SUBEXP=\cap_{\epsilon>0}DTIME(2^{n^\epsilon})\not\subseteq DTIME(p(n))$ for any polynomial $p(n)$.

So do we have $SUBEXP^{PP}\not\subseteq P/Poly$? So can we say either $SUBEXP\not\subseteq P/Poly$ or ${PP}\not\subseteq P/Poly$ holds?

I am trying to understand if $C^O\not\subseteq D$ for classes $C,O,D$ then does it follow either $C\not\subseteq D$ or $O\not\subseteq D$?

In other words if we have two classes $C,O$ with $C\subseteq D$ and $O\subseteq D$ then does it mean $C^O\subseteq D$?

  • 2
    $\begingroup$ What do you think? Have you tried proving your claim? $\endgroup$ Dec 30 '15 at 9:19
  • $\begingroup$ @YuvalFilmus I am not very sure. Take $C=P$ and $O=NP$ and clearly $P$ and $NP$ are conjectured to be in $\Sigma_2$ and $P^{NP}$ is also in $\Sigma_2$. So I do not know what to say on how to approach such problem although seems to be related to lowness of classes. $\endgroup$
    – Mr.
    Dec 30 '15 at 9:30
  • 1
    $\begingroup$ P and NP are in $\Sigma_2^P$ by definition. $\endgroup$ Dec 30 '15 at 10:12

If $D$ is low for itself ($D^D = D$) then $C,O \subseteq D$ should imply $C^O \subseteq D$, though it might depend on the exact definition of the oracle model (for resource-restricted classes there are sometimes delicate issues there). In contrast, if $D$ isn't low for itself then taking $C=O=D$ we get a counterexample.

  • $\begingroup$ Thank you. Are you saying $P/poly$ is not low for itself? otherwise we will already have an incredible result of either $SUBEXP$ not in $P/poly$ or $PP$ is not in $P/poly$ (meaning either way $PP$ is not in $P/poly$) since we know $SUBEXP^{PP}$ is not in $P/poly$? $\endgroup$
    – Mr.
    Dec 30 '15 at 10:33
  • $\begingroup$ No, I think that P/poly is low for itself, so your result follows. $\endgroup$ Dec 30 '15 at 12:01
  • $\begingroup$ isn't $PP$ not in $P/poly$ a new result (this already gives both $PSPACE$ and $NEXP$ not in $P/Poly$) correct? And possibly $\#P$ as well right? $\endgroup$
    – Mr.
    Dec 30 '15 at 21:22
  • $\begingroup$ I'm not sure I follow that part of your argument. If SUBEXP is not in P/poly, why does it follow that PP is not in P/poly? $\endgroup$ Dec 30 '15 at 21:25
  • 1
    $\begingroup$ We get exactly what you wrote: either SUBEXP is not in P/poly, or PP is not in P/poly. $\endgroup$ Dec 30 '15 at 21:29

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.