Skip to main content
1 of 3
Turbo
  • 2.9k
  • 14
  • 27

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?

Turbo
  • 2.9k
  • 14
  • 27