Welcome to MathOverflow

Question

1

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!

edited Mar 12 2011 at 1:49

LowerBounds

community wiki

3 revisions

2

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 2011 at 1:39

1

@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 2011 at 1:47

1

It is generally considered a bad idea to post too many soft questions in quick succession; they clutter the site. – Qiaochu Yuan Mar 12 2011 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 2011 at 2:02

Ryan Williams · Accepted Answer · 2011-03-12 01:53:26Z UTC

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!

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.