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

[Computational Complexity] That P ne NP proof- whats up with that?

Expand Messages
  • GASARCH
    Let me be he last on the block to tell you that an alleged proof of P ≠ NP is out there. NOT posting on it would be absurd; however, I cannot do any better
    Message 1 of 1 , Aug 9 8:40 AM
    • 0 Attachment
      Let me be he last on the block to tell you that an alleged proof of P ≠ NP is out there. NOT posting on it would be absurd; however, I cannot do any better than what Richard Lipton already posted so I point you to his post.

      So what are my uninformed views? If I was a betting man I would bet that it won't pan out. I would bet that he proved something very interesting, but not P ≠ NP. Why do I think this? This is NOT based on the author who seems to be a person to be taken seriously. Its just that the problem is so hard and we've made no progress on it since... . Hmmm, when is the last time we made progress on it? Parity not in constant depth? Other bounds on weak models? Oracles? Natural Proofs? Something from Mulmuley's program? Fagin's theorem connecting the problem to finite model theory (which is used in the alleged proof)? I would have thought we would make slow progress at first. Not sure what type- Maybe SAT ∉ DTIME(nk) for small values of k. Maybe something else.

      Scott Aaronson apparently IS a betting man. See his post on the problem.

      I was going to go to the Barriers in Computational Complexity II workshop. If the proof is correct I hope Amtrak gives refunds.

      Actually- looking over the schedule, much of it will still be relevant. If the proof is CORRECT how will that change what we teach? What we work on? Lance's book-for-the-layperson on complexity theory? (I recently proofread a chapter on what the world would be like if P=NP. He may have to remove it. Too bad, it was awesome!)

      --
      Posted By GASARCH to Computational Complexity at 8/09/2010 10:40:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.