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

<p>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:</p>

<ul>
<li>SAT' is in NP (see below!)</li>
<li>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$. </li>
<li>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}) &gt; 2k$ and let $n&gt;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$.</li>
</ul>

<p>Edit:</p>

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

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

<p>I'd also find it interesting to see a proof by blowing holes in SAT as in <a href="http://blog.computationalcomplexity.org/media/ladner.pdf">http://blog.computationalcomplexity.org/media/ladner.pdf</a>.
Without the NP requirement this is fairly easy:
there is a sequence $n_1&lt;n_2&lt;\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$.</p>

CC BY-SA 3.0
2012-12-13T22:22:49.377Z
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": http://www.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
CC BY-SA 3.0
2012-12-15T11:00:12.270Z
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
Vanessa
CC BY-SA 3.0
2012-12-16T00:24:15.493Z
@Squark: absolutely - and I also assumed Schöning's theorem didn't apply.
Colin McQuillan
CC BY-SA 3.0
2012-12-11T03:45:21.147Z
2012-12-11T14:38:10.193Z
2012-12-11T14:38:10.193Z
Colin McQuillan
<p>(NPI $\nsubseteq$ P/poly) $\implies$ (P$\neq$NP)</p>

CC BY-SA 3.0
2012-12-12T18:33:04.000Z
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
CC BY-SA 3.0
2012-12-12T18:45:44.617Z
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
CC BY-SA 3.0
2012-12-12T19:26:31.520Z
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
CC BY-SA 3.0
2012-12-12T19:43:16.160Z
the question NPI$\subseteq$P/poly inherently runs against conventional wisdom as you pointed out in your 1st comment wrt factoring and this answer reflects that; esp in cryptographic research it is probably widely believed that there are not small circuits for factoring, otherwise it would conceivably break RSA. imho (as you just corrected yourself) some implications on NPI,P/poly are not-so-obvious because the classes are not-so-mainstream. feel free to flag it for moderator deletion. but probably still lose vote pts on downvotes even if deleted (?).. maybe best of both worlds for you =)
vzn
CC BY-SA 3.0
2012-12-12T19:55:17.497Z
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
CC BY-SA 3.0
2012-12-12T21:22:33.587Z
"empty implication"? huh? P$\neq$NP is an "empty implication"? beg to disagree...
vzn
CC BY-SA 3.0
2012-12-13T04:02:28.483Z
-1: sometimes losing point feels just right
Alessandro Cosentino
CC BY-SA 3.0
2012-12-12T17:45:45.033Z
2012-12-12T18:40:40.660Z
2012-12-12T18:40:40.660Z
vzn
<p>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):</p>

<blockquote>
  <p>Uwe Schöning. <a href="http://www.sciencedirect.com/science/article/pii/0304397582901141">A uniform approach to obtain diagonal sets in complexity
  classes.</a> Theoretical Computer Science 18(1):95-103, 1982.</p>
</blockquote>

<p>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:</p>

<ul>
<li>$A_1 = \varnothing$ (or any language in $\mathsf{P}$)</li>
<li>$A_2 = \text{SAT}$</li>
<li>$\mathsf{C}_1 = \mathsf{NPC}$</li>
<li>$\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$</li>
</ul>

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

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

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

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

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

CC BY-SA 3.0
2012-12-13T15:27:14.737Z
This is a link to Schöning's publications available on-line for free, including the one you refer to: http://www.uni-ulm.de/in/theo/m/schoening/list-of-on-line-available-publications.html
Alessandro Cosentino
CC BY-SA 3.0
2012-12-15T10:57:06.193Z
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
Vanessa
CC BY-SA 3.0
2012-12-15T15:14:18.087Z
@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
CC BY-SA 3.0
2012-12-15T15:15:37.397Z
@JohnWatrous : Yes, this is precisely the reason I was confused
Vanessa
CC BY-SA 3.0
2012-12-13T14:43:12.340Z
2012-12-13T14:43:12.340Z
John Watrous
<p>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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

CC BY-SA 3.0
2012-12-08T22:04:45.377Z
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
CC BY-SA 3.0
2012-12-08T23:32:17.727Z
AFAIK, we don't know if $\mathsf{NP}\not\subseteq\mathsf{P}$ implies $\mathsf{NP}\not\subseteq\mathsf{P/poly}$, i.e. what you are asking is also not known.
Kaveh
CC BY-SA 3.0
2012-12-08T23:40:41.440Z
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
CC BY-SA 3.0
2012-12-09T00:30:31.157Z
Generalizing @Sasho Nikolov's comment one step: It is known that it's impossible to base security of one-way functions on the worst-case complexity of NP-complete problems (using non-adaptive reductions) unless the polynomial hierarchy collapses. Assuming PH doesn't collapse: Given poly-size circuits for all non-NP-complete problems, all crypto becomes much, much harder to do.
Daniel Apon
CC BY-SA 3.0
2012-12-09T01:29:18.780Z
Won't a padding argument show that this can't happen unless NP $\subseteq$ P/poly?
Peter Shor 
CC BY-SA 3.0
2012-12-09T18:21:00.593Z
@Kaveh : I clarified the formulation
Vanessa
CC BY-SA 3.0
2012-12-09T18:25:34.937Z
@PeterShor : I'm probably being dense, but how exactly would it work?
Vanessa
CC BY-SA 3.0
2012-12-09T18:46:05.310Z
@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 
CC BY-SA 3.0
2012-12-10T13:44:58.687Z
@PeterShor: Nice! It seems your argument really *needs* that gap between poly and subexp in the assumption (NPI in P/poly, but NPC not in SUBEXP/subexp), and the "slightly slower than P/poly time" in the conclusion is also necessary. You can obviously get away with a smaller gap, but the smaller the gap in the assumption the larger the gap in the conclusion (to the point where assuming only NPC not in P/poly, I think the conclusion becomes trivial). I wonder if there's a modification that doesn't need a gap, or at least with a smaller assumption-conclusion tradeoff.
Joshua Grochow
CC BY-SA 3.0
2012-12-10T13:56:02.533Z
@Joshua: yes, I need the gap. When I wrote my first comment, I had this argument in mind, but hadn't thought it through enough to realize it would require a gap.
Peter Shor 
CC BY-SA 3.0
2012-12-10T18:57:40.400Z
@PeterShor : "NP-complete problems can't be solved in subexponential time and advice" seems a very strong assumption. What evidence do we have for such a claim?
Vanessa
CC BY-SA 3.0
2012-12-11T07:03:11.760Z
Well there is the ETH (at least for the "time" part)
Suresh Venkat
<cc.complexity-theory><complexity-classes><advice-and-nonuniformity><p-vs-np><np-intermediate>
Is NPI contained in P/poly?
Vanessa
# Is NPI contained in P/poly?

(Asked by: username_0 on 2012-12-08)

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?

**Tags:** cc.complexity-theory, complexity-classes, advice-and-nonuniformity, p-vs-np, np-intermediate

> **Comments:**
> **username_1**: 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  
> **username_2**: AFAIK, we don't know if $\mathsf{NP}\not\subseteq\mathsf{P}$ implies $\mathsf{NP}\not\subseteq\mathsf{P/poly}$, i.e. what you are asking is also not known.  
> **username_2**: 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.  
> **username_3**: Generalizing @username_1's comment one step: It is known that it's impossible to base security of one-way functions on the worst-case complexity of NP-complete problems (using non-adaptive reductions) unless the polynomial hierarchy collapses. Assuming PH doesn't collapse: Given poly-size circuits for all non-NP-complete problems, all crypto becomes much, much harder to do.  
> **username_4**: Won't a padding argument show that this can't happen unless NP $\subseteq$ P/poly?  
> **username_0**: @username_2 : I clarified the formulation  
> **username_0**: @PeterShor : I'm probably being dense, but how exactly would it work?  
> **username_4**: @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.  
> **username_5**: @PeterShor: Nice! It seems your argument really *needs* that gap between poly and subexp in the assumption (NPI in P/poly, but NPC not in SUBEXP/subexp), and the "slightly slower than P/poly time" in the conclusion is also necessary. You can obviously get away with a smaller gap, but the smaller the gap in the assumption the larger the gap in the conclusion (to the point where assuming only NPC not in P/poly, I think the conclusion becomes trivial). I wonder if there's a modification that doesn't need a gap, or at least with a smaller assumption-conclusion tradeoff.  
> **username_4**: @Joshua: yes, I need the gap. When I wrote my first comment, I had this argument in mind, but hadn't thought it through enough to realize it would require a gap.  
> **username_0**: @PeterShor : "NP-complete problems can't be solved in subexponential time and advice" seems a very strong assumption. What evidence do we have for such a claim?  
> **username_6**: Well there is the ETH (at least for the "time" part)  

---

## 3 answers

### Answer by username_10 on 2012-12-13. Score: 18 | Accepted answer

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.](http://www.sciencedirect.com/science/article/pii/0304397582901141) 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.

> **Comments:**
> **username_9**: This is a link to Schöning's publications available on-line for free, including the one you refer to: http://www.uni-ulm.de/in/theo/m/schoening/list-of-on-line-available-publications.html  
> **username_0**: 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  
> **username_10**: @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.  
> **username_0**: @JohnWatrous : Yes, this is precisely the reason I was confused  

---

### Answer by username_7 on 2012-12-11. Score: 15

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

> **Comments:**
> **username_5**: 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": http://www.cs.uchicago.edu/~fortnow/papers/uniform.pdf). In fact, your proof is basically Impagliazzo's proof of Ladner, but adapted to this situation. Neat!  
> **username_0**: 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  
> **username_7**: @Squark: absolutely - and I also assumed Schöning's theorem didn't apply.  

---

### Answer by username_8 on 2012-12-12. Score: -13

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

> **Comments:**
> **username_1**: 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.  
> **username_8**: 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...  
> **username_1**: 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  
> **username_8**: the question NPI$\subseteq$P/poly inherently runs against conventional wisdom as you pointed out in your 1st comment wrt factoring and this answer reflects that; esp in cryptographic research it is probably widely believed that there are not small circuits for factoring, otherwise it would conceivably break RSA. imho (as you just corrected yourself) some implications on NPI,P/poly are not-so-obvious because the classes are not-so-mainstream. feel free to flag it for moderator deletion. but probably still lose vote pts on downvotes even if deleted (?).. maybe best of both worlds for you =)  
> **username_1**: 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.  
> **username_8**: "empty implication"? huh? P$\neq$NP is an "empty implication"? beg to disagree...  
> **username_9**: -1: sometimes losing point feels just right  

---

