Vinay Deolalikars proof of P=NP and the power of "web-test"

There are several ways of making a million dollars. One way suggested by Warren Buffett is to start with a billion dollars and invest them in an airline company. Unfortunately, for most of us this is not a practical way. There is another way which surprisingly needs no investment. Well, it needs a pencil and a paper which you can borrow from your friend. And of course, it needs your time which you can steal from your employer like Einstein did at Swiss Patent Office. Or better still, like Srinivas Ramanujam, you can make your dreams work for you. But here is the catch – you should be able to solve one of the six open problems in mathematics called the “Millennium Problems” defined by the Clay Mathematics Institute. The original list contained seven problems but one was solved by Grigory Perelman of Moscow in 2002. Three weeks back, on August 8, an HP researcher Vinay Deolalikar put up a draft of a proof sketch for one of the six Millennium Problems called “P=NP” on the Internet. Will Vinay get his million dollars?

I am supposed to have studied ABC of complexity theory in my undergraduate and graduate schools. But I pretty much don’t remember anything except for what “P” and “NP” means. Class P contains problems like sorting and searching which have fast computer programs. The other class NP contains problems which don’t have fast programs yet but if someone gives us an answer, we can write a program that can check its correctness quickly. Nobody has been able to mathematically prove whether P is equal to NP or not equal to NP. The problem is around 40 years old and was proposed by Steven Cook in 1971.

For an abstract subject like complexity theory, Prof. Richard Lipton writes amazingly lucid blog titled Godel’s lost letter and P=NP. In the months of May, June and July Richard wrote 8 blogs every month and averaged 17, 20 and 33 comments respectively on each blog entry. That’s very high for an abstract mathematical topic like complexity theory. But something even more extraordinary happened earlier this month. From Sunday 8^th August till next Sunday 15^th August Richard wrote 6 blogs on topics related to Vinay Deolalikar’s proof. Here is the list of blogs and the number of comments on each blog:

8-Aug A proof that P is not equal to NP (188 comments)

9-Aug Issues in the proof that P not equal to NP (121 comments)

10-Aug Updates on Deolalikar’s proof that P not equal to NP (184 comments)

11-Aug Deolalikar responds to issues about his P not equal to NP proof (129 comments)

12-Aug Fatal flaws in Deolalikar’s proof? (311 comments)

15-Aug P=NP “Proof” is one week old (257 comments)

That’s an average of 198 comments, roughly 8 times his average over the past 3 months. Some of the comments came from students and amateurs. But many comments came from what Richard called “The group”: Timothy Gowers, Gil Kalai, Ken Regan, Terence Tao, and Suresh Venkatasubramanian a powerful collection of top experts in the field. The Group found out three major gaps in the proof which Vinay has worked on and sent a final version for publication to a journal. Only time will tell whether his proof can fill the gaps but at this point odds are stacked against him.

Following sample comment gives us an idea of what Richard’s blog meant to readers:

I also want to thank Dick Lipton for the monumental effort. I am very thankful not only for the things already said (things learned, putting N != NP in the spotlight, etc) but also for something else that many researchers here take for granted: this was a public showing of the rigorous peer-review process that many people, specially aspiring researchers, non graduate students and amateur scientists, are unfamiliar with. For somebody attending a good university in his/her country of origin but where top notch research is not conducted, this whole exercise provided a glimpse about what’s like doing cutting edge work. Hopefully that might be a motivation to pursue a career in math or science later on.

Peer review in scientific publishing is undergoing a shift. “web-test” is becoming a powerful alternative to traditional “it-may-take-a-year” kind of review. Will review of this kind happen also in literature & social sciences? I guess so. Shakespeare Quarterly a 60-year old prestigious humanities journal is going to open its review to the web. “web-test” is still in its infancy but holds a great promise.

I would like to thank my friend D. Sivakumar for sending me the link to Richard’s blog. It is because of Siva that I can claim – I have a friend who is an expert in complexity theory!