Deolalikar P vs NP paper

Note: This is currently an UNOFFICIAL page on Deolalikar's P!=NP paper, and is not yet affiliated with a Polymath project.

This is a clearinghouse wiki page for the analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP. Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions are to be avoided. This page is derived from an earlier collaborative document created by Suresh Venkatasubramanian.

For the latest discussion on the technical points of the paper, see this thread of Dick Lipton and Ken Regan. For meta-discussion of this wiki (and other non-mathematical or meta-mathematical issues), see this thread of Suresh Venkatasubramanian.

The paper

• Vinay Deolalikar's web page
• First draft, Aug 6, 2010
• Second draft Aug 9, 2010.

Proof strategy

(Excerpted from this comment of Ken Regan)

Deolalikar has constructed a vocabulary V which apparently obeys the following properties:

1. Satisfiability of a k-CNF formula can be expressed by NP-queries over V—in particular, by an NP-query Q over V that ties in to algorithmic properties.
2. All P-queries over V can be expressed by FO+LFP formulas over V.
3. NP = P implies Q is expressible by an LFP+FO formula over V.
4. If Q is expressible by an LFP formula over V, then by the algorithmic tie-in, we get a certain kind of polynomial-time LFP-based algorithm.
5. Such an algorithm, however, contradicts known statistical properties of randomized k-SAT when k >= 9.

Possible issues

Issues with LFP

There appear to be three issues related to the use of the characterization of P in terms of first order logic, an ordering and a least fixed point operator. All of these are discussed in the Lipton/Regan post, with contributions from David Barrington, Paul Christiano, Lance Fortnow, James Gate, and Arthur Milchior.

1. Is the lack of ordering in the logical structures used to define the LFP structure a problem ? On the surface, it appears to be, since it is not known whether FO(LFP) can be used to characterize P without ordering.
2. The paper requires that a certain predicate in the FO(LFP) formula be unary, and forces this by expanding neighborhoods and constructing k-tuples of parameters to act as single parameters. It is not clear how this affects the arguments about the propagation of local neighborhoods.
3. Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?

Issues with random k-SAT

1. Whether the "condensation" stage is significant: the latest ideas from physics suggest that random [math]\displaystyle{ k }[/math]-SAT and similar CSPs don’t become hard at the clustering transition, but rather at the condensation transition where a subexponential number of clusters dominate the space of solutions. Graph coloring provides some evidence of this. Moreover, random k-XORSAT has a clustering transition, frozen variables, etc., but is of course in P. (Cris Moore and Alif Wahid)
2. Whether the solution space is indeed complex: The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". Two problems:
   1. Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions.
   2. There is a randomized reduction from SAT to formulas with at most ONE satisfying assignment (Valiant-Vazirani).

So either Valiant-Vazirani can't be derandomized or RP=NP (seems very unlikely!) or the proof must break (Ryan Williams, on twitter)

Barriers

Any P vs NP proof must deal with the three known barriers described below. The concerns around this paper have not yet reached this stage yet.

Terminology

• Finite model theory
• Immerman-Vardi theorem
• Least fixed point (LFP)
• Random k-SAT
• The complexity class NP
• The complexity class P

Online reactions

Theory blogs

• P ≠ NP, Greg Baker, Greg and Kat’s blog, August 7 2010
• A proof that P is not equal to NP?, Richard Lipton, Godel's lost letter and P=NP, August 8 2010
• On the Deolalikar proof: Crowdsourcing the discussion ?, Suresh Venkatasubramanian, The Geomblog, August 9 2010
• Putting my money where my mouth isn’t, Scott Aaronson, Shtetl-Optimized, August 9 2010
• That P ne NP proof- whats up with that?, Bill Gasarch, Computational Complexity, August 9 2010
• Issues In The Proof That P≠NP, Richard Lipton and Ken Regan, Godel's lost letter and P=NP, August 9 2010
• A relatively serious proof that P != NP ?, Antonia Porreca, August 9 2010 (aggregates all the comments)
• A 'polymath' home for analysis of the Deolalikar proof, Suresh Venkatasubramanian, The Geomblog, August 10 2010

Media and aggregators

• P ≠ NP, Hacker News, August 8 2010
• Claimed Proof That P != NP, Slashdot, August 8 2010
• P=NP=WTF?: A Short Guide to Understanding Vinay Deolalikar's Mathematical Breakthrough, Dana Chivvis, AolNews, August 9 2010
• HP Researcher Claims to Crack Compsci Complexity Conundrum, Joab Jackson, IDG News, August 9 2010

Other

• Twitter, Lance Fortnow, August 8 2010
• P<>NP?, Dave Bacon, The Quantum Pontiff, August 8 2010
• How to get everyone talking about your research, Daniel Lemire, August 9 2010
• Google Buzz, Terence Tao, August 9 2010
• P ≠ NP?, Bruce Schneier, Schneier on Security, August 9 2010.
• Vinay Deolalikar says P ≠ NP, Philip Gibbs, vixra log, August 9 2010.

Additions to the above list of links are of course very welcome.

Timeline

• August 6: Vinay Deolalikar sends out his manuscript to several experts in the field.
• August 7: Greg Baker posts about the manuscript on his blog.
• August 8: The paper is noted on Hacker News and Slashdot, and discussed on many theoretical computer science blogs.
• August 9: A second draft of the manuscript is posted.
• August 9: Suresh Venkatasubramanian collects several technical comments on the paper into a collaborative document.
• August 9: In a post of Dick Lipton and Ken Regan, several technical issues and concerns raised by various experts are discussed.
• August 10: Venkatasubramanian's document is migrated over to a wiki page.

Bibliography

• [AM2003] D. Achlioptas, C. Moore, "Almost all graphs with average degree 4 are 3-colorable", Journal of Computer and System Sciences 67, Issue 2, September 2003, Pages 441-471.
• [I1986] N. Immerman, "Relational queries computable in polynomial time", Information and Control 68 (1986), 86-104
• [VV1986] L. G. Valiant, V. V. Vazirani, "NP is as easy as detecting unique solutions", Theoretical Computer Science (North-Holland) 47: 85–93 (1986). doi:10.1016/0304-3975(86)90135-0.
• [V1982] M. Vardi, Complexity of Relational Query Languages, 14th Symposium on Theory of Computation (1982), 137-146.

Other links

• P versus NP problem - Wikipedia
• Vinay Deolalikar - Wikipedia
• Deolalikar publication list - DBLP
• Gerhard Woeginger’s P-versus-NP page