# “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

## 1 Answer

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!

-
@Ryan: Thanks, this is exactly the type/general-class of response I was looking for. (i.e. something that pushes in a direction further than what the text provided) – LowerBounds Mar 12 '11 at 2:11