ObjectHunter
Hunting and gathering in the JEE landscape

I am Frank, a freelance Java developer specialized in backend development from south western germany.

Vinay Deolalikar offers a proof for P != NP

posted by fas on 2010-08-11 . Tagged as computer science, theory

On August 6th 2010 Vinay Deolalikar sent a link to a document on the HP servers entitled P!=NP. A bold claim regarding the fact that the question wether these complexity classes is part of the millenium prize program, the quest for the greatest unsolved problems in math. But it's much to early for Vinay to gather the million dollars an accepted proof to this problem is worth.
His paper has still to undergo peer review, but other masterminds of the mathworld describe the outline for Deolalikar's proof as worth investigating: Richard Lipton a Professor of the Georgia Institue of Technology together with his collegue Ken Regan glanced over the paper and collected criticism to Deolalokar's approach on his blog.

Update: Neil Immerman might have already discovered some flaws in Deolalikar's approach to the P!=NP(?) problem, as Dick Lipton writes on his blog

Update: Scott Aaronson destroys Deolalikar's proof on his blog

Update: There is a nice video of a talk by Ken Clarkson, Ron Fagin and Ryan Williams concentrating on the problems with Deolalikar's approach to the proof.

Update: In spite of the massive critique of his proof, Deolalikar writes that he will post a complete version on his HP Labs website soon. It seems Deolalikar still trusts that his approach might produce something useable, although others have already announced the proof is poppycock. Scott Aaronson is so sure of the proof being incorrect that he offered Deolalikar $ 200,000, if his proof will be accepted in the next 9 years.

Updade: Nowadays the proof has been widely discredited.

Tags: computer science, theory