Indian-origin scientist ’solves one of world’s most complex math problems’

LONDON - Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP - one of the world’s most complex and intractable mathematical problems.

Deolalikar, who works at the research arm of Hewlett-Packard in Palo Alto, California, said that he has proven that P is not equal to NP.

The solution, if right, could earn him 1 million dollars as prize money.

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.

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.

Scott Aaronson, of Massachusetts Institute of Technology, pledged on his blog to pay Deolalikar an additional 200,000 if he is right.

“If P not equal to NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it,” The Telegraph quoted him as saying.

For instance, calculating how to accommodate 400 students in 100 university rooms.

The Clay Mathematical Institute 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.” (ANI)