[Computational Complexity] If pigs could fly then bacon would be cheaper
- Pretend you didn't know the Karp-Lipton theorem. Consider the following two statements
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.
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 falseand
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.
Posted By GASARCH to Computational Complexity at 10/03/2007 01:31:00 PM