Initially hailed as a solution to the biggest question in computer science, the latest attempt to prove P ≠ NP – otherwise known as the “P vs NP” problem – seems to be running into trouble.
Two prominent computer scientists have pointed out potentially “fatal flaws” in the draft proof by Vinay Deolalikar of Hewlett-Packard Labs in Palo Alto, California.
Since the 100-page proof exploded onto the internet a week ago, mathematicians and computer scientists have been racing to make sense of it.
The problem concerns the speed at which a computer can accomplish a task such as factorising a number. Roughly speaking, P is the set of problems that can be computed quickly, while NP contains problems for which the answer can be checked quickly. Serious hole?
It is generally suspected that P ≠ NP. If this is so, it would impose severe limits on what computers can accomplish. Deolalikar claims to have proved this. If he turns out to be correct, he will earn himself a $1 million Millennium prize from the Clay Mathematics Institute in Cambridge, Massachusetts.
Much of the excited online discussion regarding the proof has taken place on the blog of Richard Lipton, a computer scientist at the Georgia Institute of Technology with over 30 years of experience working on P vs NP.
This morning, however, Lipton posted an email from another computer scientist, Neil Immerman of the University of Massachusetts, who claims to have found a “serious hole” in Deolalikar’s paper.