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

<p>For more info, see <a href="https://link.springer.com/chapter/10.1007/3-540-56287-7_99" rel="nofollow noreferrer">"Superpolynomial circuits, almost sparse oracles and the exponential hierarchy"</a> by Buhrman and Homer.  Also, for more info on $P/poly$, see <a href="https://en.wikipedia.org/wiki/P/poly" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/P/poly</a></p>

<p>I recently started thinking about $NP/poly$.  I can't seem to find much info on this class other than the listing here: <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nppoly" rel="nofollow noreferrer">NP/poly @ Complexity Zoo</a></p>

<p>@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$.</p>

<blockquote>
  <p><strong>Question</strong></p>
  
  <p>Is $NEXP^{NP}$ known to not be contained in $NP/poly$?</p>
</blockquote>

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

CC BY-SA 3.0
2018-01-06T05:55:06.650Z
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
CC BY-SA 3.0
2018-01-06T09:41:43.890Z
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
CC BY-SA 3.0
2018-01-06T09:59:21.290Z
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
CC BY-SA 3.0
2018-01-06T18:32:07.513Z
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
CC BY-SA 3.0
2018-01-06T19:58:52.590Z
@EmilJeřábek Thank you very much!!  I really appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-06T20:10:43.923Z
@EmilJeřábek I want to make sure that I understand this correctly so please correct me if I am mistaken: so we can relativize the arguments for $P/poly$ to get corresponding results for $NP/poly$?
Michael Wehar
CC BY-SA 3.0
2018-01-06T20:16:01.340Z
@EmilJeřábek When we relativize, do we get that $NEXP^{\Sigma_2^P}$ is not contained in $NP/poly$.  Or, do we actually get the same as we got for $P/poly$ that being that $NEXP^{NP}$ is not contained in $NP/poly$?
Michael Wehar
CC BY-SA 3.0
2018-01-07T07:41:19.527Z
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
CC BY-SA 3.0
2018-01-07T17:20:49.637Z
Thank you very much for the clarification!  I really appreciate it.  :)
Michael Wehar
<cc.complexity-theory><circuit-complexity><lower-bounds><np>
Is $NEXP^{NP}$ known to not be contained in $NP/poly$?
Michael Wehar
# Is $NEXP^{NP}$ known to not be contained in $NP/poly$?

(Asked by: username_0 on 2018-01-06)

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"](https://link.springer.com/chapter/10.1007/3-540-56287-7_99) 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nppoly)

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

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, np

> **Comments:**
> **username_0**: 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.  :)  
> **username_1**: 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.  
> **username_1**: 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}$.  
> **username_1**: 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.  
> **username_0**: @EmilJeřábek Thank you very much!!  I really appreciate it.  :)  
> **username_0**: @EmilJeřábek I want to make sure that I understand this correctly so please correct me if I am mistaken: so we can relativize the arguments for $P/poly$ to get corresponding results for $NP/poly$?  
> **username_0**: @EmilJeřábek When we relativize, do we get that $NEXP^{\Sigma_2^P}$ is not contained in $NP/poly$.  Or, do we actually get the same as we got for $P/poly$ that being that $NEXP^{NP}$ is not contained in $NP/poly$?  
> **username_1**: 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}$).  
> **username_0**: Thank you very much for the clarification!  I really appreciate it.  :)  

---

## 0 answers

