The proof (rather claimed proof) is spread over hundred-odd pages. The person who did it seemed serious -- he sent it to some people who are really good in the business, to check if the proof was foolproof. The mail got forwarded in many directions and someone immediately posted it on the net (yes, I think it was a silly thing to do), and the name Vinay Deolalikar became familiar in a day. Mailboxes flooded with queries about the correctness of the proof. (I came to know about all this only yesterday, as I was traveling this weekend).
Some people were sceptical about the proof, and justifiably so. Scott Aaronson literally bet his house on it. He said in response to one comment on his post: "If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it."
That explains the seriousness of the proof. If a USD $1,000,000 prize money announced for this problem was not proof enough.
One my friend said, thank god he did not prove P is equal to NP. As that would mean all 'hard' problems in computer science have a solution that can run in a reasonable time on a computer, and many people like him (and me) would become jobless.
This is the latest update I have seen: Issues in the Proof that P≠NP (Dick Lipton's blog).
But is is not dismissing this as yet another publicity gimmick. "..the author has advanced serious and refreshingly new ideas of definite value, and deserves time and space to develop them more fully", says Lipton. Which means even if the proof is not complete, it is likely to lead us to a correct and complete proof in the near future.
The paper can be found here (pdf).
No comments:
Post a Comment