"NP has linear circuits" --> something interesting? [soft, philosophical, open] - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T02:15:12Z http://mathoverflow.net/feeds/question/58221 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58221/np-has-linear-circuits-something-interesting-soft-philosophical-open "NP has linear circuits" --> something interesting? [soft, philosophical, open] LowerBounds 2011-03-12T01:32:05Z 2011-03-12T01:53:26Z <p>Page 121 of Computational Complexity, A Modern Approach states:</p> <p>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\$.</p> <p>Context: earlier in the chapter, it is shown that \$NP \subset P/poly\$ implies PH = \$\Sigma_2^p\$.</p> <p>Question: Anyone have idea of interesting ideas/conjectures to prove assuming NP has linear size circuits?</p> <p>Where interesting =</p> <p>(1) potentially attackable (i.e. ideas of why it might be true) and</p> <p>(2) non-trivial (i.e. publishable)</p> <p>Thanks!</p> http://mathoverflow.net/questions/58221/np-has-linear-circuits-something-interesting-soft-philosophical-open/58224#58224 Answer by Ryan Williams for "NP has linear circuits" --> something interesting? [soft, philosophical, open] Ryan Williams 2011-03-12T01:53:26Z 2011-03-12T01:53:26Z <p><a href="http://www.cs.cmu.edu/~ryanw/circuit.pdf" rel="nofollow">Lance Fortnow, Rahul Santhanam and I</a> 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. </p> <p>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!</p>