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

Browse other questions tagged or ask your own question.