Deolalikar’s manuscript

Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled (or in words, “P is not equal to NP”).
(See Richard Lipton’s discussion of the paper for a download link.) After all, this paper seems to be the prime cause of all the attention.

Deolalikar’s work brings to greater attention a bunch of nice techniques that currently aren’t mainstream in computational complexity theory. The main ingredients are finite model theory, random constraint satisfaction problems, and graphical models.

I haven’t yet spent much time reading the manuscript, but it certainly passes the nonsense test: there is a serious attempt to address the main objections from Scott Aaronson’s list of impediments to proving P versus NP. Moreover, the overall approach is along the same lines that several people have been attempting: combine results from the study of random constraint satisfaction problems with techniques from finite model theory. There is a roll call of at least a dozen theoretical computer scientists that I could name here, so the approach is definitely respectable. Finally, I happen to have studied all the ingredients that are used, so although I am no expert, I can at least read the paper.

Given all this, my initial impression is that the technique used is unlikely to work to prove the desired result. The argument seems non-uniform, and proving P to be equal to NP if one is going to argue that P equals NP (in order to obtain a contradiction, as the paper does), then this requires a uniform polynomial bound for the problem under consideration. In other words, for k-SAT to be in P, there must exist a single polynomial such that every instance of size can be decided by a deterministic Turing machine in steps. On my first hasty reading, it seems that the argument is built on a series of polynomials, of increasing degree. If this is the case, then this technique would be insufficient to establish the result sought. Of course, my impression may well be wrong.

I am sceptical, but the paper is definitely worth reading, unlike the vast majority of the ones listed at Gerhard Woeginger’s P-versus-NP page.

Update 20100810: see Deolalikar’s updated paper, the clearinghouse wiki, Antonio E. Porreca’s meta-summary, and Richard Lipton’s update.

Update 20100812: clarified wording of my analysis. The best single place for a technical summary remains the clearinghouse wiki mentioned above. Much of the ongoing technical discussion is happening on Richard Lipton’s blog, see further posts Update on Deolalikar’s Proof that P≠NP and Deolalikar Responds To Issues About His P≠NP Proof, and especially the many insightful comments. For those who really can’t wait, be sure to keep checking recent changes to the clearinghouse wiki.

Update 20100813: I think the last word goes to Terence Tao, in a magisterial summary of consensus about the strategy in Deolalikar’s manuscript (in a soundbite: it doesn’t work and can’t be fixed). The objection of Timothy Gowers is also worth reading.