Issues In The Proof That P≠NP
Some further comments into the recent claimed proof that P is not equal to NP
Yuri Manin is a great mathematician, who has worked in various areas and also is well known for his many excellent expository works. He has won numerous prizes, including the Nemmers Prize in Mathematics in 1994, and the Cantor Medal in 2002. One of his quotes is:
A proof only becomes a proof after the social act of “accepting it as a proof”.
Today is a follow up to Sunday’s post on Vinay Deolalikar’s claimed P NP proof. The community is working on deciding whether or not to accept his proof as a “proof.” No one has yet had a chance to study his 102-page draft paper in full depth. (Note—this is the author’s update today, but page references up through page 77 seem to be identical with the version linked before.) We do not wish to be part of a “rush to judgment”—the author has advanced serious and refreshingly new ideas of definite value, and deserves time and space to develop them more fully.
We—Ken Regan and I—do wish to be part of the discussion of the paper, and help in any way we can to facilitate the resolution of whether it is a proof or not. Hence we have jointly written this update.
We think that Vinay Deolalikar should be thanked for thinking about this difficult problem, and for sharing his ideas with the community. Whether he got it right or not, he has tried to add to our understanding of this great problem. We need more people working on hard problems. If no one does, then they never will be solved.
Possible Issues With The Proof
Even after about one day there have been many serious comments raised about the proof. We have collected some of the main ones together. They are specific objections, that need to be answered in any subsequent development. Here we collect and summarize what seem to be four main objections. The objections are related in that they all question the author’s deduction that P = NP implies the existence of a polynomial-time algorithm of a certain specific kind, which he then argues leads to a contradiction involving rigorously-known statistical properties of random -SAT instances, for large enough . Some of the objections converge on the same point in the paper, notably Section 7.2.They seem, however, to be mathematically separate—insofar as patching one might not patch the others.
Each has been voiced by more than one reader, in comments in this and other weblogs. We’ve ordered them for ease of discussion—this is not an opinion on which is most important. This post was first drafted with the comments we saw as of 4pm EDT Monday, and apologies in advance for ones missed in the meantime. Moreover, we expect that some of the objections can be answered topically—this is already evinced by some of our referenced comments, and is a goal of the conversation we are trying to promote.
- The ordered-structure issue. This is raised by James Gate here, by Arthur Milchior here, and by David Barrington (also quoting Lance Fortnow) here. Note, however, that Barrington here and Milchoir in reply may have patched their part of this point.
For background, logical formulas can be classified according to whether they reference a presumed total order on the elements of the structures they describe. For certain logical vocabularies, such an ordering can be defined even if there is not an explicit symbol for it, so the issue doesn’t matter. This is the case for formulas characterizing NP. The class P is known to have characterizing formulas over the FO(LFP) vocabulary when the explicit order is present, but whether this is true when the order is absent is a major open question, which we addressed in this blog last April 5. It is also called a “major question” in the Ebbinghaus-Flum book referenced on page 67 of Deolalikar’s paper. The paper attempts to compensate by adding a pre-defined relation symbol “” to the vocabulary, and asserts that past this point the synthesized order relation will not be needed, but there is doubt over whether the details in the paper suffice to accomplish this.
- The paper may not handle tupling correctly. This is raised by Paul Christiano here, and is part of Barrington’s comment here.
For background, the paper requires that a certain predicate—let’s call it —in the FO(LFP) formula be unary. The formula needs, however, to express properties of -tuple of elements of the underlying structure (where it might be possible to make the same as the “” in the -SAT problem being analyzed). Standardly one passes to a new structure whose elements are -tuples over the old structure. However, this can greatly distort adjacency and distance- neighborhood relations from the original structure. The author provides results with counting arguments that aim to limit the distortion, asymptotically as the size of the (original) universe goes to infinity. However, there is fundamental doubt about whether these pieces fit together. (It is possible that the objectors are overlooking material early in section 3 of the paper that can make them fit—again we have not gone to full detail here.)
- The LFP characterization of P may not accomplish what the author needs. This is also raised by Christiano, paragraph with “More simply”, and was the cautionary point of our initial reaction here.
For background, consider the problem of determining whether a given context-free grammar derives the empty string, which is complete for P under logspace reductions, and in that sense captures polynomial-time complexity. Initialize a set to be the empty set. Then iterate the following process:
For every grammar rule with , add the variable to .
Since matches the empty string, this initially picks up all variables that derive the empty string directly. Further iterations may add more variables. The process stops and outputs the final when the last iteration goes through all the rules and finds no new variables to add. This must happen within iterations since each adds at least one new variable to . Then is the Least Fixed Point (LFP) of the iteration operation, and the problem answer is “yes” provided the start symbol of the grammar belongs to this .
One can write an FO(LFP) formula that yields this algorithm. The meta-question on which this objection is based is, must every FO(LFP) formula (for this query) yield an algorithm that is similarly tractable to analyze? Going further, does Deolalikar’s logical vocabulary in section 7.2 even have enough richness to guarantee such an algorithm at all? The paper does directly address this matter in section 7.2, but the references therein do not yet seem to cinch the argument. The two objections above may be contributing factors to the lack perceived here, but this is raised as a separate conceptual matter.
- The paper may target the wrong hardness phase of randomized -SAT. This is raised by Cris Moore here and is corroborated by Alif Wahid in reply here.
This seems to be the most mathematically detailed objection. It might show that the author’s proof strategy is on the wrong track, in advance of patching any of the other objections. It might alternately show the best road to getting surprising and concrete valuable upper-bound results about (randomized) -SAT from Deolalikar’s work, even if the lower-bound consequences are elusive. Certainly we should note the interesting succession of rigorously-proved results referenced both by Deolalikar and by these commenters.
There have been various comments critiquing other aspects of the paper, and some other long ones on the mathematical content, but these seem to be the most focused objections to now.
Suresh Venkatasubramanian has linked from his wonderful GeomBlog a “Google Doc” that similarly aims to collect evaluations of the paper. One must be a registered member of Google and log in (or be logged in) when clicking his link.
Still there remains the key question: is the proof correct? In one sense the present paper almost surely has mistakes—not just from the above objections but what one could expect of any first-draft in a breakthrough situation. The real questions are, is the proof strategy correct, and are the perceived gaps fixable?