# Science: Indian scientist proposes solution to math problem

Vinay Deolalikar, a scientist working at HP Labs in California

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 (Why P vs NP Problem is so important? Read below!). 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.

P vs NP Problem
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. 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 coworker is satisfactory (i.e., no pair taken from your coworker’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 civilization 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. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

Source: The Clay Mathematic Institute

Update:

### Indian-origin scientist’s math proof has ‘serious loopholes’

Indian-origin computer scientist Vinay Deolalikar’s answer to P vs. NP has ‘potentially fatal flaws’, some scientists have pointed out.

The claim to proof had created quite a buzz amongst mathematicians and scientists on the Internet, since it’s one of the most complex problems of the world, as declared by Clay Mathematics Institute in Cambridge, Massachusetts.

Roughly speaking, P is the set of problems that can be computed quickly, while NP contains problems for which the answer can be checked quickly.

Deolalikar claims to have proven that P is not equal to NP, which if true, would impose severe limits on what computers can accomplish.

However, Neil Immerman of the University of Massachusetts said that he found a “serious hole” in Deolalikar’s paper.

According to New Scientist, Deolalikar attempts to show that some problems are in NP but not in P (and thus that P not equal to NP) by invoking another mathematical set known as FO(LFP). Immerman says that this set can’t be used in this way, given other methods deployed in the proof.

Looking at the criticism positively, it might result in a correct solution.

A flurry of online activity on a Wiki page indicates blogs and wikis rivalling blackboards and journals – a potentially positive outcome, even if P vs. NP remains unresolved.

“The internet is making a huge difference to the way mathematicians operate. A process that might have taken weeks and weeks has taken place extremely quickly,” said Timothy Gowers of the University of Cambridge. (ANI)