# On $SUBEXP$, $PP$ and $P/poly$

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

• What do you think? Have you tried proving your claim? – Yuval Filmus Dec 30 '15 at 9:19
• @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. – T.... Dec 30 '15 at 9:30
• P and NP are in $\Sigma_2^P$ by definition. – Yuval Filmus 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.
• 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$? – T.... Dec 30 '15 at 10:33
• 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? – T.... Dec 30 '15 at 21:22