This article is more than 1 year old

P≠NP proof fails, Bonn boffin admits

Norbert Blum says his proposed solution doesn't work

Computer science boffin Norbert Blum has acknowledged that his P≠NP proof is incorrect, as a number of experts anticipated.

In a post published Wednesday to the arXiv.org page where his paper used to be, Blum, a computer science professor at the University of Bonn, said: "The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage."

A discussion thread on Stack Exchange's Theoretical Computer Science forum outlines some of the issues with Blum's proof.

The P≠NP problem [PDF] is one of The Clay Mathematics Institute's seven Millennium Prize Problems, which the group characterizes as some of the most difficult math problems being puzzled over at the close of the second millennium.

It asks whether there's a class of problems where it's easy to check the solution, but it's difficult to come up with a solution.

As an example, the math group cites the Hamiltonian Path Problem: Given N cities to visit, how can this be done without visiting a city twice?

The Clay Mathematics Institute is offering $1m in prize money for solutions to these problems.

Scientists and mathematicians have been trying to prove either that P≠NP or P=NP for years, without success. There have been over 100 failed attempts, which no doubt informed the skepticism that greeted Blum's proposed solution in mid-August.

Scott Aaronson, a computer science professor at the University of Texas in Austin who expressed doubts about Blum's proof, offered this explanation for his ennui on his blog:

"I'm searching in vain for the right way to teach the nerd world to get less excited about these claims, to have the same reaction that the experts do, which is 'oh boy, not another one' – which doesn't mean that you know the error, or even that there is an error, but just means that you know the history," he wrote.

Toward that end, Aaronson recently acquired the domain haspvsnpbeensolved.com, which now hosts a simple web form where one can input a link to an academic paper and receive an answer to the question "Has P vs NP been solved yet?"

In accordance with Aaronson's incredulity and joke code written by Adam Chalmers, a developer for RetailMeNot, the answer is always, "No. Our analysis algorithm has generated the following Bayesian prediction: the URL that you provided does not, in fact, point to a solution to the P vs NP problem."

Blum did not immediately respond to a request for comment. ®

More about

TIP US OFF

Send us news


Other stories you might like