4
$\begingroup$

To the best of my knowledge, it is known that $NEXP^{NP} \nsubseteq P/poly$, but it's still not known if $NEXP \nsubseteq P/poly$.

For more info, see "Superpolynomial circuits, almost sparse oracles and the exponential hierarchy" by Buhrman and Homer. Also, for more info on $P/poly$, see https://en.wikipedia.org/wiki/P/poly

I recently started thinking about $NP/poly$. I can't seem to find much info on this class other than the listing here: NP/poly @ Complexity Zoo

@EmilJeřábek suggested in the comments below that $MA$-$EXP^{NP} \cap coMA$-$EXP^{NP}$ (and further $NEXP^{\Sigma_2^P}$) is known to not be contained in $NP/poly$ by relativizing the arguments for $P/poly$.

Question

Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

Note: Question was updated to reflect @EmilJeřábek's comments below.

$\endgroup$
  • $\begingroup$ When I say smallest complexity class, I mean among non-trivial, somewhat natural complexity classes such as those listed in complexity zoo. But, really, any notable complexity class that is known to not be contained in NP/poly is worth mentioning. Thank you. :) $\endgroup$ – Michael Wehar Jan 6 '18 at 5:55
  • 1
    $\begingroup$ The smaller class MA-EXP $\cap$ coMA-EXP is also not included in P/poly. Something similar one level up should work for NP/poly. $\endgroup$ – Emil Jeřábek Jan 6 '18 at 9:41
  • 4
    $\begingroup$ Actually, it seems one does not have to go one level up, almost the same class works: I didn’t work out the details, but I think that the standard argument can be modified to yield $\mathrm{PSPACE\subseteq NP/poly\implies PSPACE=AM}$, which means that $\mathrm{AM\text-EXP\cap coAM\text-EXP\nsubseteq NP/poly}$. $\endgroup$ – Emil Jeřábek Jan 6 '18 at 9:59
  • 1
    $\begingroup$ I missed an important detail in the argument; now I don't know how to get AM, only $\mathrm{MA^{NP}}$ (which is no better than just relativizing the standard argument with an NP oracle). More precisely, I can express PSPACE by a predicate of the form $\exists(\mathrm{coNP\land AM})$. Anyway, at the very least, $\mathrm{MA\text-EXP^{NP}\cap coMA\text-EXP^{NP}}$ is not included in NP/poly. $\endgroup$ – Emil Jeřábek Jan 6 '18 at 18:32
  • 1
    $\begingroup$ We get that $\mathrm{MA\text-EXP^{NP}\cap coMA\text-EXP^{NP}}$ is not contained in NP/poly. That's also a subclass of $\mathrm{NEXP^{\Sigma^P_2}}$ (i.e., $\Sigma_3^{EXP}$). $\endgroup$ – Emil Jeřábek Jan 7 '18 at 7:41

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.