I very much agree with this quote in “A Tale of A Serious Attempt At P≠NP” by Richard J. Lipton – (August 15, 2010)
“… I learned that the Internet may not replace referees yet, but it can raise many important questions in a positive and constructive manner.”
With respect to the P != NP “proof”, I am not optimistic. Quoting “The problem of P versus NP” (full article enclosed below),
“Mr. Deolalikar has submitted a revised proof, but Dr. Cook believes the jig is up. Does he believe P vs. NP will ever be solved? “Yes, I do, I do – eventually. But not very soon. I think it really is a hard problem. It’s becoming increasingly clear, because so many top mathematicians have tried to solve it.””
“The problem of P versus NP – Kate Allen From Saturday’s Globe and Mail – Published on Friday, Aug. 20, 2010 10:28PM EDT
In 1971, Dr. Stephen Cook, a young University of Toronto professor in the fledgling field of computer science, posed a theoretical problem so intractable it has become the subject of a $1-million prize. Since then, only a handful of credible solutions have been posed. All of them fell short. This month, one man caused a commotion after he announced to experts in the field that he had solved the problem known as P vs. NP.
Vinay Deolalikar, a Delhi-born mathematician at Hewlett-Packard, sent Dr. Cook and two dozen other experts in the field an e-mail, writing, “I am pleased to announce a proof that P is not equal to NP, which is attached.” The paper was more than 100 pages long. Dr. Cook was excited. In 40 years, “I can think of only a couple of other attempts of people who’ve thought they’ve proved it,” Dr. Cook said. “Most of them you can dismiss very easily – they’re not really mathematicians. But this one was much more serious.”
Clay Mathematics Institute, the Cambridge, Mass.-based academy that offers the $1-million prize, describes the problem with this example: Imagine you are trying to figure out housing for 400 university students. Read the rest of this entry »