SAT has poly size circuits.
The Poly Hierarchy collapses.You probably think both are false. Which statements truth would surprise you more? Personally I think SAT has poly size circuits would surprise me more.
Karp-Lipton Theorem:
If SAT has poly size circuits then Poly Hierarchy Collapses.Does this really make your belief that SAT does not have poly sized circuits stronger? You already believed that. I know of one theorists who tells me that she believes SAT does not have poly sized circuits MUCH MORE than she believes that PH does not collapse. Hence this theorem does not tell her anything.
If you have
(unbelievable statement A) --> (unbelievable statement B)what do we then know that we didn't know before? We know that A is MORE unbelievable than B, I suppose. We seem to have taken
BLAH --> P=NPas the gold standard in showing that we believe BLAH is false and
BLAH --> PH=\Sigma_2^p
BLAH --> PH=\Sigma_2^petc. as forming a hierarchy of non-belief.
This is a nice picture, but it may be that BLAH is just not that believable in its own right and does not need to imply something like $\PH = \Sigma_3^p$ to give NOT(BLAH) street cred.
the karp-lipton theorem -is- one of the (chronologically first) reasons why we believe circuits cant solve hard problems. i dont see any intuition why SAT couldnt have polysize circuits otherwise.
ReplyDeleteYou see no reason to believe that P/poly != NP other than the karp-lipton theorem?
ReplyDeleteThis isn't so different a statement from P != NP, and basically all of Scott's "Reasons to Believe" (http://www.scottaaronson.com/blog/?p=122) still apply.
In Her wisdom, Nature may not agree with Scott's reasons.
ReplyDeleteThis is entirely counter-intuitive.
ReplyDeleteThe cost of hog enclosures would have to go up in order to keep the pigs from escaping by flight. I don't see how this could do anything but increase the price of bacon.
Karp-Lipton is a great theorem -- but as Bill points out, not because it helps convince us that SAT doesn't have small circuits. (We knew that already. :-) )
ReplyDeleteRather it's a great theorem because, along with LFKN and the Bshouty et al. learning algorithm, it gives one of the few known bridges between uniform and nonuniform complexity -- and thereby lets us prove interesting circuit lower bounds (for example, that Sigma2P doesn't have linear-size circuits).