Vinay Deolalikar

New Delhi, Aug. 11: Mathematical circles seem abuzz with shades of curiosity, excitement as well as scepticism over a claim by Indian-born engineer Vinay Deolalikar that he has proved one of the most important unresolved problems of mathematics.

Deolalikar, a principal research scientist at HP Labs in the US, last week sent out a manuscript to fellow mathematicians, claiming he has a proof that P is not equal to NP, an exceptionally difficult problem formulated in 1971 that has remained unsolved.

The P versus NP problem — as mathematicians have labelled it — shows through rigorous mathematical formalism that it is always easier to determine whether a candidate solution to a mathematical problem is correct or not, rather than attempting to work out a solution to the problem from scratch.

The Clay Mathematical Institute in the US has listed the P versus NP problem as one of seven so-called Millennium Problems, and offered a prize of $1 million for solutions.

The manuscript by Deolalikar is currently circulating among mathematicians for independent scrutiny and assessment, a key step to validate the proof.

“It is over 100 pages long and it could take some days before mathematicians can look at all the steps and determine whether it is a correct proof or not,” said Chandan Saha, a computer science scholar from the Indian Institute of Technology, Kanpur, who is heading for a postdoctoral position in Germany.

“We’ll have to wait — if it is correct, it’ll be big,” said Saha.

But already there are voices of scepticism. Scott Aaronson, an associate professor of computer science at the Massachusetts Institute of Technology in the US, is so sceptical that he has pledged in his blog to pay Deolalikar an additional $200,000 if the solution is accepted by Clay.

At least two computer scientists in the US have identified four problems with his proof which they expect Deolalikar to answer. “Whether he got it right or not, he has tried to add to our understanding of this great problem,” Richard Lipton said in a blog. “We need more people working on hard problems. If no one does, then they never will be solved.”

The Clay Mathematical Institute has tried to explain the P versus NP problem through an example of a task in which a group of 400 university students need to be accommodated in space for 100, and where certain pairs of students are incompatible.

Instead of trying to figure out all possible ways to accommodate students, it is easier to check whether a given solution of 100 students fits in with the rules of accommodation.

One of the outstanding problems in computer science is finding questions whose answers can be quickly checked, but which need an impossibly long time to solve through any direct procedure.