# “NP has linear circuits” --> something interesting? [soft, philosophical, open]

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!

• MO is not for homework questions: it does not matter if it's not homework for you, by the way, professors should be able to assign this problem without the answer being spoiled by MO. – Thierry Zell Mar 12 '11 at 1:39
• @Thierry: My understanding from the question is that it is not a real "homework question" but rather an open problem posed in the textbook as an exercise... – Ryan Williams Mar 12 '11 at 1:47
• It is generally considered a bad idea to post too many soft questions in quick succession; they clutter the site. – Qiaochu Yuan Mar 12 '11 at 1:52
• @Ryan: my bad, though it still sounds like the authors intended it as an exercise in personal reflection, than, say, bibliography. – Thierry Zell Mar 12 '11 at 2:02

Lance Fortnow, Rahul Santhanam and I 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!