August 12, 2010

Experts Challenge Solution To “˜P vs NP’ Problem

Scientists are challenging claims by a California mathematician that he has solved the long-standing "P vs. NP" problem, one of the most difficult unsolved riddles of computer science.

Dr. Vinay Deolalikar of Hewlett-Packard laboratories says he has solved the long-standing question, one of seven Millennium Prize Problems set out by the Clay Mathematics Institute.

The Institute has offered a $1 Million award for anyone who solves any of the problems, which they described as the most difficult in the field of mathematics.

However, math experts are now challenging what they say are flaws in Dr. Deolalikar's proof, which was published in a detailed manuscript available on Hewlett Packard's Website.

Dr. Deolalikar said his equations demonstrated "the separation of P from NP."

If he is correct, he will be the first person to have proven that there is a distinct difference between a problem's correct solution and actually generating its correct answer.

In an interview with BBC News, MIT computer scientist Scott Aaronson explained why the problem is so important.

"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 essentially asks the question: If a problem exists in which one could recognize the correct answer if given, is there a 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," Dr. Aaronson said.

"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's proof says that it cannot.

Solving the P vs. NP could have "enormous applications", said Dr Aaronson, and would reveal whether there is a way to solve computational problems in which the correct answer is recognizable.  Airline scheduling, for instance, might be one potential application.

However, the new proof may fail a "very simple sanity check," Dr. Aaronson explained.

One way to test a mathematical proof is to ensure that it only proves things we know are true, he said.

"It had better not also prove something that we know to be false."

Other experts have weighed in on Dr. Deolikar's manuscript by requesting him to show that his proof passes this test.

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


On the Net: