By now, everyone in computer science and operations research is aware of the purported P<>NP proof of Vinay Deolalikar of HP Labs. After intense discussion (mainly through blogs and wikis), the original paper was taken down, and Vinay has prepared a new version for submission. He claims:
I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers. I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website.
I am convinced by Dick Lipton’s blog entry and by Scott Aaronson’s commentary suggesting fundamental flaws in the paper, but since Vinay has not retracted the paper, I will look forward to the definitive version of the paper. For a detailed description of the issues, press coverage, and other aspects, polymath has an extensive wiki on the topic.
What I find most intriguing is the field’s response to this claimed proof. Proofs that P=NP or P<>NP are certainly not uncommon. Gerhard Woeginger faithfully keeps track of these claims and is up to 62 in his list. Some of these results come out of the operations research world. For instance, Moustapha Diaby is a faculty member at the business school at the University of Connecticut and believes he has found linear programming formulations for NP-hard problems (number 17 on Woeginger’s list).
The Deolalikar paper is unique, however, in that many, many top mathematicians looked very closely at the paper and worked very hard to determine its correctness. This group includes people like Fields-medal winner Terrence Tao and Polya and Fulkerson prize winner Gil Kalai. Why did so many very smart people (and successful! They don’t do wikipedia pages on just anyone [yet]) spend time on this while practically no one spends time with the other 61 purported proofs?
The most obvious reason is that this paper presented a fundamentally new approach to this problem. As Lipton says: “the author has advanced serious and refreshingly new ideas of definite value”. In this proof, Deolalikar uses finite model theory, an area of logic, to deduce structures in random satisfiability problems. If P=NP, then the structures would have to be different than what is already known about random satisfiability problems in the critical region (this synopsis is vague to the point of not being usable). This is definitely a different direction than past efforts, bringing together a number of disparate fields.
Further, Deolalikar knows very well that there are a number of proofs in the literature that say “P<> NP cannot be proved this way”. For instance, any result that cannot distinguish between the easy 2-satisfiability and the hard 3-satisfiability is doomed to failure (Aaronson’s blog entry gives a few others along with other signs to check for in claimed proofs). Deolalikar presented reasons for believing that his approach evaded the barriers. This leads to excitement! Could this approach avoid known invalid approaches?
Contrast this with papers that suggest that a linear programming model can correctly formulate an NP-complete problem. Yannakakis showed that no symmetric formulation can do so, and that provides a powerful barrier to linear programming formulations. Not only must a a formulation not be symmetric, but its asymmetry must be of the sort that continues to evade Yannakakis’ proof. Without a strong argument on why an LP formulation fundamentally avoids Yannakakis’ argument, it is not even worthwhile spending time with LP formulations of NP-complete problems.
This overwhelming doubt was clearly not felt by some referees who allowed Diaby’s papers to be published in “International Journal of Operational Research”, lending credence to the idea that the refereeing and journal process in operations research is broken (in my view, of course). For the steps given in the Computational Complexity blog, we have have to add a step: “Your paper is accepted by a third tier journal and still no one believes it.” Similarly, it will not be enough for me to see that Deolalikar’s paper is published: at this point I trust the blogs (some of them, anyway) more than the journals!
Even if the Deolalikar result is shown not to be valid, the paper gives me enormous hope that someday the P<>NP (as I believe it is, rather than P=NP) will be proved. We appear to be developing methods that will have some traction in the area.
One thought on “P versus NP and the Research Process”