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

  • 3
    $\begingroup$ 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$? $\endgroup$ – Sasho Nikolov Dec 22 '17 at 13:07
  • 2
    $\begingroup$ You should really ask the questions you are interested in then. $\endgroup$ – Sasho Nikolov Dec 22 '17 at 14:11
  • 1
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Dec 22 '17 at 14:22
  • 3
    $\begingroup$ See for example Miltersen Vinodchandran and Watanabe 99 $\endgroup$ – Ryan Williams Dec 22 '17 at 16:40
  • 3
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 22 '17 at 17:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.