tag:blogger.com,1999:blog-3722233.post3670196677585762071..comments2023-03-29T09:38:56.563-05:00Comments on Computational Complexity: If pigs could fly then bacon would be cheaperLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-85444492151944993822007-10-04T10:21:00.000-05:002007-10-04T10:21:00.000-05:00Karp-Lipton is a great theorem -- but as Bill poin...Karp-Lipton is a great theorem -- but as Bill points out, <I>not</I> because it helps convince us that SAT doesn't have small circuits. (We knew that already. :-) )<BR/><BR/>Rather 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).Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67864818127951711762007-10-04T09:22:00.000-05:002007-10-04T09:22:00.000-05:00This is entirely counter-intuitive. The cost of ho...This is entirely counter-intuitive. <BR/><BR/>The 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77827432952417534912007-10-03T17:11:00.000-05:002007-10-03T17:11:00.000-05:00In Her wisdom, Nature may not agree with Scott's r...In Her wisdom, Nature may not agree with Scott's reasons.Keahttps://www.blogger.com/profile/05652514294703722285noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10769539291730314472007-10-03T14:47:00.000-05:002007-10-03T14:47:00.000-05:00You see no reason to believe that P/poly != NP oth...You see no reason to believe that P/poly != NP other than the karp-lipton theorem?<BR/><BR/>This 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78618494964185779882007-10-03T14:32:00.000-05:002007-10-03T14:32:00.000-05:00the karp-lipton theorem -is- one of the (chronolog...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.Anonymousnoreply@blogger.com