# Constraints

## 9 August 2010

### Deolalikar’s manuscript

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

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.

## 2 Comments	»

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

Pingback by — 10 August 2010 @ 16:10

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 — 13 August 2010 @ 20:43

RSS feed for comments on this post. TrackBack URI

Theme: Rubric. Blog at WordPress.com.

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 4, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9165456891059875, "perplexity_flag": "middle"}