0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What do you think? Have you tried proving your claim? $\endgroup$
    – Yuval Filmus
    Commented Dec 30, 2015 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$
    – Turbo
    Commented Dec 30, 2015 at 9:30
  • 1
    $\begingroup$ P and NP are in $\Sigma_2^P$ by definition. $\endgroup$
    – Yuval Filmus
    Commented Dec 30, 2015 at 10:12

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • $\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$
    – Turbo
    Commented Dec 30, 2015 at 10:33
  • $\begingroup$ No, I think that P/poly is low for itself, so your result follows. $\endgroup$
    – Yuval Filmus
    Commented Dec 30, 2015 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$
    – Turbo
    Commented Dec 30, 2015 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$
    – Yuval Filmus
    Commented Dec 30, 2015 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$
    – Yuval Filmus
    Commented Dec 30, 2015 at 21:29

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.