1
$\begingroup$

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!

$\endgroup$
4
  • 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$ Mar 12, 2011 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$ Mar 12, 2011 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$ Mar 12, 2011 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$ Mar 12, 2011 at 2:02

1 Answer 1

7
$\begingroup$

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!

$\endgroup$
1
  • $\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$ Mar 12, 2011 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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