Monday, August 09, 2010

That P ne NP proof- whats up with that?

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!)

14 comments:

  1. Rather than pontificate, why don't you just read the proof already?

    ReplyDelete
  2. Glancing on the paper I would say that the "proof" doesn't seem rigorous enough.
    Most of the text is dedicated to known definitions and restating known theorems. I haven't seen much of a "proof" work there.

    ReplyDelete
  3. A "what if P=NP" chapter seems like it would still be interesting. Maybe just change it to a "what if P had been equal to NP" like a comic book "what if" story.

    An undergradutate algorithms course wouldn't change much. Understanding what NP and NPC are still matters. You lose a few minutes of "what if they are the same" talk. If you do approximation algorithms, they are just a tiny bit more important perhaps.

    I was told once, in song, something to the effect that if you proved P was NP tonight, there would still be papers left to write. Is there a song for "P wasn't NP"?

    ReplyDelete
  4. Rather than pontificate, why don't you just read the proof already?

    Why don't YOU read the proof if you care so much. I doubt Bill wants to proofread yet another attempt, especially when there are others out there who clearly will.

    Bill posted information for the readers in case anyone had not heard about it and linked to two discussions that he feels are worthwhile. I thank him for that.

    ReplyDelete
  5. Most of the text is dedicated to known definitions and restating known theorems. I haven't seen much of a "proof" work there.

    100+ pages, this is a full proof attempt, defining and explaining the prior work on which it is built. Are your thoughts on Wiles' proof the same at a glance?

    ReplyDelete
  6. 100+ pages, this is a full proof attempt, defining and explaining the prior work on which it is built. Are your thoughts on Wiles' proof the same at a glance?

    I disagree.

    1. The paper is only ~60 pages (in 11pt font and standard margins).

    2. The prior work is not explained in a sufficiently rigorous manner. A random example: a theorem of Immerman and Vardy (Theorem 3.14) is stated. It uses the term "query". However, the notion of "query" is not defined in the paper. (Correct me if I'm wrong here.) Also, the text is full of verbal explanations, but seems to lack in definitions. (I'm not trying to play the paper down, I'm just describing my concerns.)

    3. I'm not working in number theory. So I can't say anything about Wiles' paper. But I'm familiar with contemporary complexity theory, and this paper doesn't seem rigorous enough. This doesn't say it is wrong of course.

    ReplyDelete
  7. Alarm bells went off in my head when he started talking about physics and statistics.

    ReplyDelete
  8. http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/

    http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html

    ReplyDelete
  9. I bet most of the fun of the P=NP chapter will still be there if you allow for practical nondeterministic machines (perhaps some quantum hand waving?). For instance, you'd still have perfect speech recognition, and rapid proof generation.

    ReplyDelete
  10. http://www.saudigazette.com.sa/index.cfm?method=home.regcon&contentID=2008062910436

    ReplyDelete
  11. Huh? What does Dr. Kamouna has to do with anything here?

    ReplyDelete
  12. I like the idea of "what if"

    ReplyDelete
  13. http://www.deccanherald.com/content/66125/den-corruption.html

    http://www.livemint.com/2009/09/13230728/Bribery-delays-underline-need.html

    ReplyDelete
  14. http://scottaaronson.com/blog/?p=456#comment-45277

    Ahmet Canbolat comments---
    Also, I seriously condemn Turkish academic society for turning Turkish higher education sytem into a crap and corrupt environment, consisting of only vomiting the information you memorized in lectures into paper. Is there any one aware of this from Turkish math and CS scientists.
    ---

    Indian education is same thing.
    Vinay Deolalikar vomited the information he memorized in 20 years of lectures in India and in extremely respectable Indian Institute of Technology into his paper(s).

    ReplyDelete