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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.