# Constraints

## 9 August 2010

### Deolalikar’s manuscript

Filed under: Commentary — András Salamon @ 17:39
Tags: ,

Given the sudden influx of visitors, it seemed apposite to talk about Vinay Deolalikar’s manuscript titled $P \ne NP$ (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 $p(x)$ such that every instance of size $n$ can be decided by a deterministic Turing machine in $p(n)$ 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.