# On $i.o.P/poly$?

1. Is $NEXP^{NP}\not\subseteq i.o.P/poly$?

2. Is there any consequence if $NP$ or $PP$ is in $i.o.P/poly$?

Showing $NEXP^{NP}\not\subseteq P/poly$ needs Karp-Lipton.

What is the best $i.o.P/poly$ lower bound result we know? As of this writing this is $EXP^{\Sigma_2P}\not\subseteq i.o.P/poly$.

• Doesn't EXPSPACE contain this function cstheory.stackexchange.com/a/22183/4896, whose intersection with $\{0,1\}^n$ has circuit complexity $2^{n/2}$ for every $n$? – Sasho Nikolov Dec 22 '17 at 13:07
• You should really ask the questions you are interested in then. – Sasho Nikolov Dec 22 '17 at 14:11
• For your modified question: isn't the exponential time hierarchy contained in EXP$^{PP}$ by a scaled up version of Toda's theorem? And wouldn't that answer your question for the same reason that I pointed out above? – Sasho Nikolov Dec 22 '17 at 14:22
• See for example Miltersen Vinodchandran and Watanabe 99 – Ryan Williams Dec 22 '17 at 16:40
• EXP$^{\Sigma_2^P}$ contains the language in the answer I linked in my first comment: see Emil's comments under the answer. That language is designed to have exponential circuit complexity for all $n$. If EXP$^{PP}$ indeed contains the exponential hierarchy, then it will contain EXP$^{\Sigma_2^P}$, and the same language. – Sasho Nikolov Dec 22 '17 at 17:08