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.



  1. […] Salamon is also “sceptical“, as “the technique used is unlikely to work to prove the desired result”. […]

    Pingback by A relatively serious proof that P ≠ NP? « Antonio E. Porreca — 10 August 2010 @ 16:10 | Reply

  2. […] ≠ NP) consequences Filed under: Uncategorized — András Salamon @ 20:36 During the discussion about Vinay Deolalikar’s manuscript, many people commented about the consequences that would follow if we knew that P ≠ NP. I’d […]

    Pingback by P not equal to NP (P ≠ NP) consequences « Constraints — 13 August 2010 @ 20:43 | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Blog at

%d bloggers like this: