"NP has linear circuits" --> something interesting? [soft, philosophical, open] - MathOverflow

"NP has linear circuits" --> something interesting? [soft, philosophical, open]

2011-03-12T01:32:05Z

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!

Answer by Ryan Williams for "NP has linear circuits" --> something interesting? [soft, philosophical, open]

2011-03-12T01:53:26Z

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!