It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$. However, the proof doesn't seem to generalize to $\mathsf{P}/\text{poly}$ so the possibility $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ i.e. $\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$ seems open.Assuming $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ (or even that the polynomial hierarchy doesn't collapse on any level), is $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ known to be true or  false? What evidence can be put for and against it?
Is NPI contained in P/poly?
cc.complexity theory;complexity classes;advice and nonuniformity;p vs np;np intermediate
Here is a possible alternative to a padding argument, based on Schning's generalization of Ladner's theorem. To understand the argument, you need to have access to this paper (which will unfortunately be behind a pay wall for many):Uwe Schning. A uniform approach to obtain diagonal sets in complexity  classes. Theoretical Computer Science 18(1):95-103, 1982.We will apply the main theorem from that paper for $A_1$ and $A_2$ being languages and $\mathsf{C}_1$ and $\mathsf{C}_2$ being complexity classes as follows:$A_1 = \varnothing$ (or any language in $\mathsf{P}$)$A_2 = \text{SAT}$$\mathsf{C}_1 = \mathsf{NPC}$$\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$For the sake of clarity, the fact we will prove is $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ implies $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.Under the assumption that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ we have $A_1\not\in\mathsf{C}_1$ and $A_2\not\in\mathsf{C}_2$. It is clear that $\mathsf{C}_1$ and $\mathsf{C}_2$ are closed under finite variations. Schning's paper includes a proof that $\mathsf{C}_1$ is recursively presentable (the precise definition of which can be found in the paper), and the hardest part of the argument is to prove that $\mathsf{C}_2$ is recursively presentable.Under these assumptions, the theorem implies that there exists a language $A$ that is neither in $\mathsf{C}_1$ nor in $\mathsf{C}_2$; and given that $A_1\in\mathsf{P}$, it holds that $A$ is Karp-reducible to $A_2$, and therefore $A\in\mathsf{NP}$. Given that $A$ is in $\mathsf{NP}$ but is neither $\mathsf{NP}$-complete nor in $\mathsf{NP} \cap \mathsf{P/poly}$, it follows that $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.It remains to prove that $\mathsf{NP} \cap \mathsf{P/poly}$ is recursively presentable. Basically this means that there is an explicit description of a sequence of deterministic Turing machines $M_1, M_2, \ldots$ that all halt on all inputs and are such that $\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$. If there is a mistake in my argument it is probably here, and if you really need to use this result you will want to do this carefully. Anyway, by dovetailing over all polynomial-time nondeterministic Turing machines (which can be simulated deterministically because we don't care about the running time of each $M_k$) and all polynomials, representing upper bounds on the size of a Boolean circuit family for a given language, I believe it is not difficult to obtain an enumeration that works. In essence, each $M_k$ can test that its corresponding polynomial-time NTM agrees with some family of polynomial-size circuits up to the length of the input string it is given by searching over all possible Boolean circuits. If there is agreement, $M_k$ outputs as the NTM would, otherwise it rejects (and as a result represents a finite language).The basic intuition behind the argument (which is hidden inside Schning's result) is that you can never have two nice complexity classes (i.e., ones with recursive presentations) being disjoint and sitting flush against each other. The topology of complex classes won't allow it: you can always construct a language properly in between the two classes by somehow alternating between the two for extremely long stretches of input lengths. Ladner's theorem shows this for $\mathsf{P}$ and $\mathsf{NPC}$, and Schning's generalization lets you do the same for many other classes.