Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] If pigs could fly then bacon would be cheaper

Expand Messages
  • GASARCH
    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
    Message 1 of 1 , Oct 3, 2007
    • 0 Attachment
      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.

      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=NP
      as the gold standard in showing that we believe BLAH is falseand
      BLAH --> PH=\Sigma_2^p
      BLAH --> PH=\Sigma_2^p
      etc. 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
    Your message has been successfully submitted and would be delivered to recipients shortly.