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

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.

• 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. :) – Michael Wehar Jan 6 '18 at 5:55
• 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. – Emil Jeřábek Jan 6 '18 at 9:41
• 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}$. – Emil Jeřábek Jan 6 '18 at 9:59
• 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. – Emil Jeřábek Jan 6 '18 at 18:32
• 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}$). – Emil Jeřábek Jan 7 '18 at 7:41