Million dollar maths puzzle sparks row

By Victoria Gill
Science reporter, BBC News

Image caption,
P vs NP has been described as the biggest unsolved problem in computer science

A claim to have solved one of the most difficult riddles in mathematics has been challenged by scientists.

Vinay Deolalikar, a mathematician based at Hewlett-Packard laboratories in California, US, claims to have solved the problem of P vs NP.

This has been described as the biggest problem in computer science; it is one of seven Millennium Prize Problems set out by the Clay Mathematics Institute.

But maths experts have weighed in to point out flaws in his proof.

Clay has offered one million US dollars in prize money for the solution of each of these problems, which they declared to be the most difficult in maths.

Dr Deolalikar published his proof in a detailed manuscript, which is available on the HP website. His equations, he said demonstrated "the separation of P from NP".

If this is the case, Dr Deolalikar will be the first person to have proven that there is a difference between recognising the correct solution to a problem and actually generating the correct answer.

Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology (MIT) in the US, explained to BBC News why this problem was so significant.

"People sometimes use the analogy of a jigsaw - it can be hard to complete the jigsaw, but if someone has done it, it's pretty easy to check - you just look at it," he said.

P vs NP poses the following question: If there is a problem that has this property - whereby you could recognise the correct answer when someone gives it to you - then is there some way to automatically find that correct answer?

"There's always one way a computer can find the answer- just by trying all the possible combinations one by one," said Dr Aaronson.

"But if you're trying to break a cryptographic code, for example, that could take an astronomical amount of time.

"P vs NP is asking - can creativity be automated?"

Dr Deolalikar claims that his proof shows that it cannot.

It may seem esoteric, but solving P vs NP could have "enormous applications", according to Dr Aaronson.

From cracking codes to airline scheduling - any computational problem where you could recognise the right answer, this would tell us if there were a way to automatically find that answer.

'Sanity test'

But Dr Aaronson says the new proof may fail a "very simple sanity check".

One way to test a mathematical proof, he said, is to ensure that it only proves things we know are true. "It had better not also prove something that we know to be false."

Other mathematicians have responded to Dr Deolikar's paper by asking him to show that his proof passes this test.

"Everyone agrees, said Dr Aaronson, "if he can't answer this, the proof is toast."

More on this story

Related Internet Links

The BBC is not responsible for the content of external sites.