Monday, August 9, 2010

Vinay Deolalikar and P vs. NP


The mathematics and computer science blogs are a-buzzin' about Vinay Deolalikar's unverified 100+ page proof that P does not equal NP. This paper is still a draft, and in a very preliminary form. Vinay happens to be a graduate of the University of Southern California. His advisor was P. Vijay Kumar. Dick Lipton talks about it in his blog, as do Scott Aaronson, and Greg Baker. Dave Bacon talks about it over at the Quantum Pontiff blog. I did read a little bit of the paper, and there do seem to some new ideas there. Scott has said that if the proof is correct, i.e., P <> NP, he will supplement an extra $200,000! As you wil recall this problem is one of the famous Clay Millenium Prize problems, and the Clay institute will award one million dollars to the person who solves it. The correctness of this proof would be quite remarkable. I just don't think that the problem's end time as arrived yet. I can place the hardness of this problem on an equal footing with other hard problems such as graph isomorphism, the Riemann Hypothesis, Navier-Stokes etc. Graph theory and complex analysis have been around for well over a hundred years. They are both mature fields of study, where as theoretical computer science has been around for only forty years. Vinay's purported proof must have some groundbreaking calculations and insights to arrive at the final result. The journey in this case is equally as important as the end result. I do hope that the proof is correct.