There was a lot of buzz this weekend about a paper claiming to resolve the “P vs NP” conjecture. I’ve seen plenty of papers claiming to do this over the years, so I didn’t rush to track it down. But as the tweeting continued, I decided to have a quick look for myself, if only to produce a crotchety blog post on the matter.
Part of the drama around this paper comes from the way it appeared. Author Vinay Deolalikar‘s web page explains:
Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. The preliminary version made it to the web without my knowledge. I have made minor updates, here. Please note that the final version of the paper is under preparation, and is to be posted here very shortly.
I’m a global health researcher now, so I’m not going to be the one who tries to verify this 104 page paper, but I would love to learn from a careful review that it is true. The result seems to go further than separating P and NP, since it is a statement about a natural distribution of instances being hard (from p. 78):
If LFP were able to compute solutions to the d1RSB phase of random k-SAT, then the distribution of the entire space of solutions would have a substantially simpler parametrization than we know it does.
Ryan Williams thinks this is suspicious, and expressed his concern in a series of tweets:
- This P vs NP claim is getting tons of press. I am really doubtful that it works. Hard to convey my skepticism in a tweet, but here goes…
- The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a “hard structure”. Two problems:
- (2) There is a randomized reduction from SAT to formulas with at most ONE satisfying assignment (Valiant-Vazirani). A simple solution space
- So either Valiant-Vazirani can’t be derandomized or RP=NP (seems very unlikely!) or the proof must break. That’s my intuition.
Time will tell. I find proof of the existence of hard-on-average distributions much more exciting than plain old P vs NP, and Deolalikar’s paper might have something for everybody.