Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
so, "what would happen if all problems in NP are either NP-complete or in P\poly"? for one thing it would imply small circuits for factoring –  Sasho Nikolov Dec 8 '12 at 22:04
ps: the post would be more readible if you spell out "it" in the quoted part. Also you may want to use $\mathsf{NP}\not\subseteq\mathsf{P/poly}$ in place of $\mathsf{NP}\not\subseteq\mathsf{P}$ as your assumption. –  Kaveh Dec 8 '12 at 23:40
Won't a padding argument show that this can't happen unless NP $\subseteq$ P/poly? –  Peter Shor Dec 9 '12 at 1:29
@PeterShor : I'm probably being dense, but how exactly would it work? –  Squark Dec 9 '12 at 18:25
@Squark: you're not being dense ... I hadn't worked out exactly how it would work, and I think I mis-stated the result slightly. But here's my basic idea. Suppose that NP-complete problems can't be solved in subexponential time and advice. Take an NP-complete problem X, and pad it so that the fastest algorithm for it is barely subexponential. Then it's NPI, so it can be solved in P/poly. This means the NP-complete problem X can be solved in time only slightly slower than P/poly time. By polynomial reduction, now all NP-complete problems can be solved in slightly slower than P/poly time. –  Peter Shor Dec 9 '12 at 18:46
show 7 more comments

3 Answers

up vote 16 down vote accepted

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.

share|improve this answer
This is a link to Schöning's publications available on-line for free, including the one you refer to: uni-ulm.de/in/theo/m/schoening/… –  Alessandro Cosentino Dec 13 '12 at 15:27
Thanks a lot for your answer! The funny thing is, I knew Shoening's theorem but for some foolish reason thought it doesn't apply in this case. Btw, the text is freely available even in sciencedirect –  Squark Dec 15 '12 at 10:57
@Squark: It isn't foolish to suspect that Schöning's theorem doesn't apply, given that P/poly includes non-recursive languages. I suppose it's good fortune that we can intersect it with NP and still get the result. –  John Watrous Dec 15 '12 at 15:14
@JohnWatrous : Yes, this is precisely the reason I was confused –  Squark Dec 15 '12 at 15:15
add comment

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


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

share|improve this answer
After seeing @JohnWatrous's answer, I was reminded of Impagliazzo's proof of Ladner's Theorem by padding (cf. the appendix of Downey and Fortnow "Uniformly Hard Languages": cs.uchicago.edu/~fortnow/papers/uniform.pdf). In fact, your proof is basically Impagliazzo's proof of Ladner, but adapted to this situation. Neat! –  Joshua Grochow Dec 13 '12 at 22:22
Thanks a lot for your answer! I apologize I haven't selected it but I had to pick one and Watrous' argument was easier to follow through since it used a result I already knew. This is a rather subjective way to choose but I couldn't do any better. Anyway it's great to have more than one way to arrive at an interesting result –  Squark Dec 15 '12 at 11:00
@Squark: absolutely - and I also assumed Schöning's theorem didn't apply. –  Colin McQuillan Dec 16 '12 at 0:24
add comment

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

share|improve this answer
it is both known and trivial: if P = NP, then $\mathsf{NPI} \subseteq \mathsf{NP} = \mathsf{P} \subseteq \mathsf{P/pol}$. also this is not the question, the question is the converse of what you wrote, and was convincingly answered by Colin as far as I can see. –  Sasho Nikolov Dec 12 '12 at 18:33
the question is entitled "is NPI contained in P/Poly" & think this is a reasonable answer, not sure its really trivial because of the way NPI is usually defined (as dependent on P$\neq$NP)... this answer does not conflict with the other answer... –  vzn Dec 12 '12 at 18:45
Actually it is even more obviously trivial: if P=NP, NPI is empty. The question is clearly stated as "does NP not contained in P/poly imply NPI not in P/poly. So your answer 1) claims that a trivial fact is an open problem 2) does not address the question –  Sasho Nikolov Dec 12 '12 at 19:26
Could not care less about points. For the last time: my first comment, Colin's answer, and the question itself are related to the far less trivial and more interesting converse of the empty implication you wrote down. –  Sasho Nikolov Dec 12 '12 at 19:55
-1: sometimes losing point feels just right –  Alessandro Cosentino Dec 13 '12 at 4:02
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.