Deolalikar P vs NP paper: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
→‎Terminology: added a link for FO in a descriptive complexity setting
Line 63: Line 63:
* [http://en.wikipedia.org/wiki/Finite_model_theory Finite model theory]
* [http://en.wikipedia.org/wiki/Finite_model_theory Finite model theory]
* [[Immerman-Vardi theorem]]
* [[Immerman-Vardi theorem]]
* [http://en.wikipedia.org/wiki/Least_fixed_point Least fixed point] (LFP)
* [http://en.wikipedia.org/wiki/Least_fixed_point Least fixed point] (LFP) in general, and in a [http://en.wikipedia.org/wiki/FO_(complexity)#Least_Fixed_Point_is_PTIME descriptive complexity setting]
* [[Random k-SAT]]
* [[Random k-SAT]]
* [[The complexity class NP]]
* [[The complexity class NP]]

Revision as of 07:10, 10 August 2010

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, and to aggregate various pieces of news and information about this paper. 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 or speculations 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

These links are taken from Vinay Deolalikar's web page.

  1. First draft, Aug 6, 2010
  2. Second draft Aug 9, 2010.

Typos and minor errors

  • (Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via Blake Stacey)
  • (Second draft) Some (but not all) of the instances of the [math]\displaystyle{ O() }[/math] notation should probably be [math]\displaystyle{ \Theta() }[/math] or [math]\displaystyle{ \Omega() }[/math] instead, e.g. on pages 4, 9, 16, 28, 33, 57, 68, etc. (via András Salamon)

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 FO(LFP) 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. (No, it is known that parity can not be expressed without an ordering even with LFP, hence P is not captured without order [AVV1997, page 35]. But in chapter 7 this issue seems to disappear since he introduces a successor relation over the variables [math]\displaystyle{ x_1\lt \dots\lt x_n\lt \neg x_1\lt \dots\lt \neg x_n }[/math] )
  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, Alif Wahid, and Lenka Zdeborova)
  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.

Relativization

Natural proofs

Algebraization

Terminology

Online reactions

Theoretical computer science blogs

Media and aggregators

Real-time searches

Other

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

Timeline

Bibliography

Other links

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Deolalikar_P_vs_NP_paper&oldid=3321"