P=NP problem: the claim, the hype and the mini-furore

P=NP problem: the claim, the hype and the mini-furore

Bangalore: Less than a fortnight after the computing world woke up to an HP Labs researcher’s claim that he had cracked the most important unsolved question in theoretical computer science—whether P equals NP—hopes are waning as experts question if the paper even provided a strategy to finding an answer, let alone the answer itself.

Professor Manindra Agrawal explains the importance of the P equals NP problem to fundamental science and why he believes Deolalikar’s claim of having solved it to be imprecise.

Download link here

While there has been frantic online repudiation of Vinay Deolalikar’s claim that P is not equal to NP, computer scientists in India, fed up of their countrymen staking claims to answers as profound as P equals NP and as pedestrian as low-cost computers, have come together in refuting such assertions.

“We are getting tired of all these tall Indian claims, right from $10 tablets to mathematical theorems," says V. Vinay, president of the Indian Association of Research in Computing Science and founder-chairman of LimberLink Technologies Pvt. Ltd. “India deserves better than just hype."

It’s a bit unfortunate that the paper has been made public without the author working out all the details, says Manindra Agrawal, professor at the Indian Institute of Technology at Kanpur, and one of the 20-odd researchers who first received the manuscript from Deolalikar on 6 August.

“I’ve been in touch with Deolalikar. His paper claims a number of observations without giving proofs," says Agrawal.

Mint reported on Deolalikar’s claim on 11 August.

Both Agrawal and Vinay study complexity theory, the study of resources and their efficiencies in computation. And the problem of P equals NP is critical in understanding the complexity of computation.

The theorem posits that if P refers to a set of easy problems and NP refers to a set of tough problems, then P equals NP would mean that tough problems have relatively easy solutions.

In the last decade, this theorem has garnered much attention as computer science has become more foundational, indirectly impacting how we understand physics. This probably explains the overwhelming response to Deolalikar’s claim which, eventually, culminated in a mini-furore.

“While the paper itself is more than 100 pages long, Deolalikar’s contribution is not more than a dozen pages; and in them, his main contribution is remarkably sketchy and imprecise. This was quite clear to all of us (complexity theorists) from Day 1," Vinay and Agrawal said.

Recipient of several awards, including the Fulkerson Prize and the 2008 Infosys Mathematics Prize, Agrawal adds: “It is fair to say that the paper really has no proof at all in the traditional sense."

Several phone calls and emails to Deolalikar asking if he was retracting his paper or fixing gaps remained unanswered.

Lance Fortnow, a professor of electrical engineering and computer science at Northwestern University in the US, agrees with Agrawal that the “proof was quite sketchy".

“I don’t believe that Deolalikar’s approach will settle the P vs NP problem," argues Fortnow. “People have found numerous problems, big and small, with the paper, and many of us were quite sceptical from the start that such an approach would work."

Equally unconvinced is Russell Impagliazzo, a complexity theorist at University of California in San Diego. “Deolalikar has promised a subsequent version which addresses some of the criticisms. While it is conceivable that this new version will clarify and correct all the flaws in the previous one, I personally do not expect much improvement."

Still, if there’s any upside to all this, it is, according to Vinay, the “very public view of science" that people got to see. “It will provide impetus to youngsters to keep their interest alive."