Deolalikar P vs NP paper: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
Geomblog (talk | contribs)
69 edits
Line 30: Line 30:
# Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?
# Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?


=== Issues with d1RSP ===
=== Issues with random k-SAT ===
 
 
# Whether the "condensation" stage is significant: the latest ideas from physics suggest that random  $k$-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 [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-49M05RK-3&_user=10&_coverDate=09%2F30%2F2003&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=13eae49445b87797b1f90aa42e54b5a5 provides some evidence of this]. Moreover, random k-XORSAT has a clustering transition, frozen  variables, etc., but is of course in P.


=== Barriers ===
=== Barriers ===

Revision as of 00:01, 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.


The paper

Proof strategy

(Excerpted from this comment of Ken Regan.)

Deolalikar has constructed a vocabulary V such that:

  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

  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 $k$-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.

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

Theory blogs

Other

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.

Other links

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