Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP

A computer scientist claims to have solved one of the world’s most complex and intractable mathematical problems by proving that P≠NP.

Vinay Deolalikar, who works at the research arm of Hewlett-Packard in Palo Alto, California, believes he has solved the riddle of P vs NP in a move that could transform mankind’s use of computers as well as earn him a $1m (£650,000) prize.

P vs NP is one of the seven millennium problems set out by the Massachusetts-based Clay Mathematical Institute as being the “most difficult” to solve.

Many mathematical calculations involve checking such a large number of possible solutions that they are beyond the current capability of any computer. However, the answers to some are quick and easy to verify as correct. P vs NP considers if there is a way of arriving at the answers to the calculations more quickly in the first place.

Mr Deolalikar claims to have proven that P, which refers to problems whose solutions are easy to find and verify, is not the same as NP, which refers to problems whose solutions are almost impossible to find but easy to verify.

His paper, posted online on Friday, is now being peer-reviewed by computer scientists.

Scott Aaronson, associate professor of computer science at the Massachusetts Institute of Technology, is so sceptical that he pledged on his blog to pay Mr Deolalikar an additional $200,000 (£125,000) if the solution is accepted by Clay.

He wrote that he could barely afford the sum, but explained: “If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it.”

The P vs NP problem was formalised in 1971 by mathematicians Stephen Cook and Leonid Levin.

To help understand the issue, the Clay Mathematical Institute gives an example in calculating how to accommodate 400 students in 100 university rooms.

It says: “To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.

“This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a co-worker is satisfactory (i.e., no pair taken from your co-worker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical.

“Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe.

“Thus no future civilisation could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students.

“However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure.”

via Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP - Telegraph.

Not so fast...

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. ...

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."

via BBC