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!

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