Page 121 of Computational Complexity, A Modern Approach states:


6.11 (Open Problem) Suppose make a stronger assumption than $NP \subset P/poly$: every langauge in NP has linear size circuits. Can we show something stronger than PH = $\Sigma\_2^p$.


Context: earlier in the chapter, it is shown that $NP \subset P/poly$ implies PH = $\Sigma\_2^p$.


Question:
 Anyone have idea of interesting ideas/conjectures to prove assuming NP has linear size circuits?


Where interesting =


(1) potentially attackable (i.e. ideas of why it might be true) and


(2) non-trivial (i.e. publishable)


Thanks!



"NP has linear circuits" --> something interesting? [soft, philosophical, open]
[Lance Fortnow, Rahul Santhanam and I](http://www.cs.cmu.edu/~ryanw/circuit.pdf) have shown some nontrivial results in this direction. For example, $NP$ has $O(n^c)$ size circuits for some fixed $c$ if and only if $P^{NP[n]}$ has $O(n^k)$ size circuits for some fixed $k$. The paper has several results along these lines, so if you're interested in the generic problem of proving that $NP$ doesn't have linear size circuits, it may be a good place to get started thinking about it. 


Perhaps an even better open question is: what interesting consequences can be derived from the assumption that $NP$ has $10n$ size circuits? Even with fixed leading constants like $10$, we are still stuck!


