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!)
Rather than pontificate, why don't you just read the proof already?
ReplyDeleteGlancing on the paper I would say that the "proof" doesn't seem rigorous enough.
ReplyDeleteMost of the text is dedicated to known definitions and restating known theorems. I haven't seen much of a "proof" work there.
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.
ReplyDeleteAn 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"?
Rather than pontificate, why don't you just read the proof already?
ReplyDeleteWhy 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.
Most of the text is dedicated to known definitions and restating known theorems. I haven't seen much of a "proof" work there.
ReplyDelete100+ 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?
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?
ReplyDeleteI 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.
Alarm bells went off in my head when he started talking about physics and statistics.
ReplyDeletehttp://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/
ReplyDeletehttp://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html
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.
ReplyDeletehttp://www.saudigazette.com.sa/index.cfm?method=home.regcon&contentID=2008062910436
ReplyDeleteHuh? What does Dr. Kamouna has to do with anything here?
ReplyDeleteI like the idea of "what if"
ReplyDeletehttp://www.deccanherald.com/content/66125/den-corruption.html
ReplyDeletehttp://www.livemint.com/2009/09/13230728/Bribery-delays-underline-need.html
http://scottaaronson.com/blog/?p=456#comment-45277
ReplyDeleteAhmet 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).