Deolalikar P vs NP paper

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

The paper

• Vinay Deolalikar's web page
• First draft (date?)
• Second draft (date?)

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

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

• Least fixed point (LFP)

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

Other

• Twitter Lance Fortnow - August 8 2010
• Google Buzz Terence Tao - August 9 2010