Tide Turns Against Million-Dollar Maths Proof

Dn19313-1_300 Jacob Aron in New Scientist:

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.