A mathematics problem with a $1-million prize attached to it and one which has major implications in computer applications, like security and machine intelligence, is claimed to have been solved by an Indian working in the United States.
Vinay Deolalikar, a scientist working at HP Labs in California, has proposed a solution to the problem, commonly called by mathematicians as ‘Is P=NP?,' in a paper he has published online. The problem is one of the seven listed by the Clay Mathematics Institute for the Millennium Prize worth $1 million, which will be awarded to the successful solver of each problem.
The problem refers to the possible equivalence of two classes of problems. ‘NP' problems refer to those that may take different amounts of time to solve, based on the size of the data. But each solution suggested can be checked easily. An example given on www.nature.com is the solution of jigsaw puzzles — it is easy to verify if a solution is correct but to solve the jigsaw puzzle itself may be very difficult.
‘P' problems are those that scale in polynomial time with the size of the data. An example is the problem of alphabetically sorting a list of names. A computer can be programmed to sort the names very fast; and adding many more names will make the task difficult only to an extent and it will still be possible for the computer to handle it.
Mr. Deolalikar's solution, a 100-page proof published online, says ‘P' is in fact not the same as ‘NP.' This means computer security systems in their current form may be pretty robust to conventional computer-based attacks, but this also means some problems cannot be solved by simply throwing a lot of computer power at them.
The proof has generated a lot of interest among mathematicians, and some have started looking at the proof to see whether it will hold. But as Richard Lipton points out, quoting mathematician Yuri Manin, on his blog rjlipton.wordpress.com: “A proof becomes a proof after the social act of accepting it as a proof,” and Mr. Deolalikar has to wait for the paper to be published in a refereed journal after mathematicians vet it.
Interestingly, in March this year, another of the problems — the Poincare conjecture — was declared solved by Grigoriy Perelman, but the mathematician refused to accept the $1-million award.
