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)


  • 2
    $\begingroup$ 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. $\endgroup$ – Thierry Zell Mar 12 '11 at 1:39
  • 1
    $\begingroup$ @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... $\endgroup$ – Ryan Williams Mar 12 '11 at 1:47
  • 1
    $\begingroup$ It is generally considered a bad idea to post too many soft questions in quick succession; they clutter the site. $\endgroup$ – Qiaochu Yuan Mar 12 '11 at 1:52
  • $\begingroup$ @Ryan: my bad, though it still sounds like the authors intended it as an exercise in personal reflection, than, say, bibliography. $\endgroup$ – 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!

  • $\begingroup$ @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) $\endgroup$ – LowerBounds Mar 12 '11 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.