Is NPI contained in P/poly?

Question

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?

Answer 1

Here is a possible alternative to a padding argument, based on Schöning'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 Schöning. 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. Schöning'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 Schöning'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 Schöning's generalization lets you do the same for many other classes.

Answer 2

I'd just like to write down some version of a padding argument as described in the comments. I don't see why a gap is needed. We want to show that if NP is not contained in P/poly then there is an NP-intermediate problem not contained in P/poly.

There is an unbounded function $f$ such that SAT does not have circuits of size less than $n^{f(n)}$, and so there is a function $g$ that is unbounded, increasing, and $g(n)=o(f(n))$. Let SAT' denote the language obtained by padding SAT strings of length $n$ to $n^{g(n)}$. Then:

• SAT' is in NP (see below!)
• SAT' is not in P/poly: given circuits of size $n^k$ for SAT', we get circuits of size $n^{g(n)k}$ for SAT, but this is less than $n^{f(n)}$ for some $n$.
• There is no P/poly reduction from SAT to SAT': suppose for contradiction that there are circuits $C_n$ of size $n^k$ for SAT, allowing SAT' gates. Pick $N$ large enough that $g(\sqrt{N}) > 2k$ and let $n>N$. Each SAT' gate in $C_n$ has at most $n^k$ inputs. By removing the padding inputs we can trim the SAT' gates in $C_n$ to a SAT gate with less than $\sqrt{n}$ inputs, which we can simulate using $C_{\sqrt{n}}$ - the resulting SAT' gates have at most $n^{k/2}$ inputs. Repeating this and treating $C_N$ by hand, SAT would have circuits of about size $O(n^k n^{k/2} n^{k/4} \dots) \approx O(n^{2k})$ which is less than $n^{f(n)}$ for some $n$.

Edit:

The choice of $g$ is slightly fiddly. If you are happy putting SAT' in the promise version of NP, this bit is unnecessary.

Define $f(n)$ to be the maximum integer such that there is no circuit of size $n^{f(n)}$ for length $n$ strings for SAT. Define $g(n)$ by an algorithm that calculates $f(m)$ for $m=1,2,\dots$ and stops after time $n$ or when $m=n$, and returns the floor of the square root of the highest value found in this time. So $g(n)$ is unbounded and $\liminf g(n)/f(n)=0$ and $g(n)$ can be computed in time $n$. Now note that the above arguments only rely on SAT having no circuits of size $n^{f(n)}$ for infinitely many $n$.

I'd also find it interesting to see a proof by blowing holes in SAT as in http://blog.computationalcomplexity.org/media/ladner.pdf. Without the NP requirement this is fairly easy: there is a sequence $n_1<n_2<\dots$ such that no circuit os size $(n_k)^k$ detects SAT strings of length $n$; restrict SAT to strings of length $n_{2^{2^i}}$ for some $i$.

Answer 3

(NPI $\nsubseteq$ P/poly) $\implies$ (P$\neq$NP)