Blog

Vinay Deolalikar, a scientist at HP (Hewlett-Packard) Labs in California, has proposed a possible proof for the famed P=NP problem in mathematics—a feat that could net him $1 million (`4.6 crore) for solving one of the seven Clay Mathematics Institute Millennium Problems.

Deolalikar has released his 100-page proof online, and in a 6 August email to his “fellow researchers”, he wrote: “This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.”

The paper still needs to be published in a major refereed journal and then be “generally accepted” by the mathematical community within two years of publication for Deolalikar to collect his Clay prize.

But experts have agreed, after preliminary readings, that his paper is an effort worthy of study.

Stephen Cook, who has written the official description of the P=NP problem for the Clay Institute, has called it “a relatively serious claim to have solved P vs NP”.

The P=NP problem is, in a sense, a meta-problem—a problem about problems—with particular relevance to computer science. The “P” in this equation refers to a class of problems; if the time needed to solve a problem does not grow exponentially with the data given, the problem is a type-P problem. An NP problem, on the other hand, is one for which you can check whether a proposed solution is really a solution in reasonable—or “polynomial”—time.

Verifying a solution, it should be pointed out, is different from solving it. One can verify, with a glance, whether a jigsaw puzzle has been completed accurately or not.

But the process of completing the jigsaw itself—the solution—is longer and more involved.

The P=NP problem questions whether an NP problem is the same as a P problem.

In other words, if a problem has solutions that can be verified in polynomial time, then can the problem also be solved in polynomial time?

Ever since the problem was stated, independently, by Cook and Leonid Levin in 1971, mathematicians have thought that P does not, in fact, equal NP—but no acceptable proof of that inequality has been found.

Deolalikar’s proof, which seeks to establish that P is not equal to NP, has, in only a few days, churned up considerable excitement within the mathematical community.

An unofficial Wiki page has sprung up, detailing not only the salient aspects of Deolalikar’s paper, but also the possible problems with it. A number of computational mathematics blogs have also begun to dissect the proof. “(T)here remains the key question: is the proof correct?” wonders Richard Lipton, a computer science professor at Georgia Tech University, on his blog Gödel’s Lost Letter and P=NP. “In one sense, the present paper almost surely has mistakes—not just from the above objections, but what one could expect of any first draft in a breakthrough situation. The real questions are, is the proof strategy correct, and are the perceived gaps fixable?”

If Deolalikar’s proof is published and finds the “general acceptance” that the Clay Institute requires, it will be the second of the seven Millennium problems to have fallen within the last few years.

In March, the Clay Institute announced a prize to the Russian mathematician Grigoriy Perelman for the “resolution of the Poincaré conjecture”. Perelman, however, chose to turn down the award.