Polymath Wiki - User contributions [en]

Deolalikar P vs NP paper

2010-08-12T04:02:42Z

MciprianM:

This is a clearinghouse wiki page for aggregating the following types of items:

# Analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP;
# News and information about this preprint;
# Background material for the various concepts used in the preprint; and
# Evaluation of the feasibility and limitations of the general strategies used to attack P != NP, including those in the preprint.

It is hosted by the [[Main Page|polymath project wiki]], but is not a formal polymath project.

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 [https://docs.google.com/document/edit?id=1uOa3BE7oK8Q7iEuOZ1EfkS16lF_Um1VwyMgdzrjZuT0&hl=en&authkey=COS65rkE earlier collaborative document] [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html created by Suresh Venkatasubramanian].

== Discussion threads ==

The main discussion threads are being hosted on Dick Lipton's blog. Several of the posts were written jointly with Ken Regan.

* [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ A proof that P is not equal to NP?], August 8 2010. (Inactive)
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ Issues In The Proof That P≠NP], August 9 2010. (Inactive)
* [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/ Update on Deolalikar's Proof that P≠NP], August 10 2010. (Inactive)
* [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/ Deolalikar Responds To Issues About His P≠NP Proof] August 11, 2010 ('''Active''')

== The paper ==

These links are taken from [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ Vinay Deolalikar's web page].

* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf First draft], Aug 6, 2010
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf Second draft] Aug 9, 2010. '''File removed,''' Aug 10 2010.
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated-mjr.pdf draft 2 + ε], Aug 9 2010. '''File removed,''' ( Aug 12? 2010 ).
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf Third draft], Aug 11 2010.

Here is the list of [[Update|updates]] between the different versions.

== Typos and minor errors ==

Any typos appearing in an earlier draft that no longer appear in the latest draft should be struck out.

* <strike>(Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via [http://scottaaronson.com/blog/?p=456#comment-44783 Blake Stacey])</strike>
* (Second draft) Some (but not all) of the instances of the <math>O()</math> notation should probably be <math>\Theta()</math> or <math>\Omega()</math> instead, e.g. on pages 4, 9, 16, 28, 33, 57, 68, etc. (via [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4530 András Salamon])
** Still present in the third draft, e.g. "O(n) Hamming separation between clusters" occurs on page 68 and similarly in several other places.
* (Second draft, page 27) <math>n 2^n</math> independent parameters → <math> n 2^k</math> independent parameters
* (draft 2 + e, p.34, Def. 3.8): <math>n</math> → <math>k</math>
* (Second draft, page 52) <math>\sum C_{li}S_i-k>0</math> → <math>\sum C_{li}S_i+k>0 </math>
* (draft 2 + e, p.10): "We reproduce the rigorously proved picture of the 1RSB ansatz that we will need in Chapter 5." The phrasing makes it sound like we will need the 1RSB ansatz in Chapter 5 instead of saying that it is reproduced in Chapter 5 (which I think is what the author intended). One fix is to move "in Chapter 5" to the beginning of the sentence.
* (Third draft, p. 102): "inspite" → "in spite"

== Proof strategy ==

(Excerpted from [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4491 this comment of Ken Regan])

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

# 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.
# All P-queries over V can be expressed by FO(LFP) formulas over V.
# NP = P implies Q is expressible by an FO(LFP) formula over V.
# 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.
# Such an algorithm, however, contradicts known statistical properties of randomized k-SAT when k >= 9.

===An alternate perspective===
[http://scottaaronson.com/blog/?p=456#comment-44844 Leonid Gurvits]:
<blockquote>
...the discrete probabilistic distributions in the paper can be viewed
as tensors, or very special multilinear polynomials.
The assumptions “P=NP” somehow gives a (polynomial?)
upper bound on the tensor rank. And finally, using
known probabilistic results, he gets nonmatching
(exponential?) lower bound on the same rank.

If I am right, then this approach is a very clever, in a good sense
elementary, way to push the previous algebraic-geometric approaches.
</blockquote>

== Possible issues ==

=== Issues with LFP ===

[http://www.logic.rwth-aachen.de/~graedel/ Erich Grädel] has an [http://www.logic.rwth-aachen.de/pub/graedel/FMTbook-Chapter3.pdf extensive review of finite model theory and descriptive complexity].

There appear to be 4 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 [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ Lipton/Regan post], with contributions from David Barrington, Paul Christiano, Lance Fortnow, James Gate, Arthur Milchior, Charanjit Jutla, Julian Bradfield and Steven Lindell.

* Is the lack of ordering in the logical structures used to define the LFP structure a problem (since parity can not be expressed without an ordering even with LFP, hence P is not captured without order).
::In chapter 7 this issue seems to disappear since he introduces a successor relation over the variables <math>x_1<\dots<x_n<\neg x_1<\dots<\neg x_n</math>.
:: If it was possible to express k-SAT in FO(NLFP,without succ) (NLFP=non deterministic LFP) or in relational-NP, as introduced in [[http://portal.acm.org/citation.cfm?id=256295 AVV1997]] then by an extension of the Abiteboul-Vianu theorem it would be enough to prove that k-SAT is not in FO(LFP,without succ). This would avoid the problem of the order
* '''The issue of tupling''': 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.
::[http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np#comment-4828 Albert Atserias says], "...for someone knowing the finite model theory used in the paper, there is a jump in the reasoning that lacks justification. This is the jump from Monadic LFP to full LFP. The only justification for this crucial step seems to be Remark 7.4 in page 70 of the original manuscript (and the vague statement in point 3 of page 49), but this is far from satisfactory. The standard constructions of the so-called canonical structures that Vinay refers to (see Ebbinghaus and Flum book in page 54) have a Gaifman graph of constant diameter, even without the linear order, due to the generalized equalities that allow the decoding of tuples into its components. Issues along these lines were raised before [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/#comment-4677 here] and [http://scottaaronson.com/blog/?p=456#comments in comment 54 here]
::[http://www.haverford.edu/cmsc/slindell/ Steven Lindell] presents a [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4898 detailed critique of this problem], with an indication that there might be insurmountable problems. It is reproduced [[Lindell's Critique | here]] for completeness.
* Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4737 Charanjit Jutla] has pointed out that the argument in section 4.3 (with which several other people have also had issues) depends on the absence of a greatest fixed point. "This is a usual mistake most people new to fixed-point logics fall prey to. For example, now he has to deal with formulas of the kind <math>\nu x (f(y, x) \and g(y, x)).</math> Section 4.2 deals with just one least fixed point operator…where his idea is correct. But, in the next section 4.3, where he deals with complex fixed point iterations, he is just '''hand waving''', and possibly '''way off'''."
:: A few comments later, [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4801 he appears to revise this objection], while bringing up a new issue about the boundedness of the universe relating to the LFP operator.

=== Issues with phase transitions ===

''A brief synopsis of the terms discussed can be found [[Random_k-SAT|here]]''

# '''The nomenclature of phase transitions''': In the statistical physics picture, there is not a single phase transition, but rather a set of different well defined transitions called '''clustering (equivalently d1RSB)''', '''condensation''', and '''freezing''' ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4723 Florent Krzakala] and [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4633 Lenka Zdeborova]). In the current version of the paper, properties of d1RSB (clustering), and freezing are mixed-up. Whereas following the established definitions, and contrary to some earlier conjectures, it is now agreed that some polynomial algorithms work beyond the d1RSB (clustering) or condensation thresholds. Graph coloring provides some evidence of this when one [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 compares the performance of algorithms] with the [http://arxiv.org/abs/0704.1269 statistical physics predictions.] The property of the solution space of random K-SAT the paper is actually using is called freezing. It was [http://arxiv.org/abs/0704.1269 conjectured] in the statistical physics community ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4723 Florent Krzakala], [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4633 Lenka Zdeborova] and [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4661 Cris Moore]) that really hard instances appears in the frozen phase, i.e. when all solutions have non-trivial cores. Existence of such a region was proven rigorously by Achlioptas and Ricci-Tersenghi and their theorem appears as Theorem 5.1 in the paper.
# '''The XOR-SAT objection ''': The conjecture that frozen variables make a problem hard is however restricted to NP-complete problems such as K-SAT and Q-COL. Indeed a linear problem such as random k-XORSAT also has a clustering transition, frozen variables, etc., and is not easy to solve with most algorithms, but is of course in P as one can use Gauss elimination and exploit the linear structure to solve it in polynomial time ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4505 Cris Moore], [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np#comment-4518 Alif Wahid], and [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4633 Lenka Zdeborova]). Similar problem might exists in other restricted CSP which are in P, but may exibit freezing stage, as pointed by several other people.
# '''The error-correcting codes objection''': Initiated in a [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4839 comment by harrison]: If I understand his argument correctly, Deolalikar claims that the polylog-conditional independence means that the solution space of a poly-time computation can’t have Hamming distance O(n) [presumably he means \theta(n)], as long as there are “sufficiently many solution clusters.” This would preclude the existence of efficiently decodable codes at anything near the Gilbert-Varshamov bound when the minimum Hamming distance is large enough.

===Issues with random k-SAT===
# '''Complex solution spaces are uncorrelated with time complexity'''. (The below is a greatly expanded version of a series of twitter comments by Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]) The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". For certain parameterizations, the space of satisfying assignments to a random k-SAT instance has some intriguing structure. If SAT is in P, then SAT can be captured in a certain logic (equivalent to P in some sense). The author claims that anything captured in this logic can't have a solution space with this intriguing structure. There are two "meta" objections to this. One is that "intriguing structure in the solution space is not sufficient for NP hardness". The second is that "intriguing structure is not necessary for NP hardness". They don't actually point to a place where the proof is wrong. But they do appear to give an obstacle to the general proof method.
## Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions. In fact it is not hard to design 2-SAT formulas (in this case not random, but specifically designed ones) so that they have exponentially many clusters of solutions, each cluster being "far" from the others, etc. That is, the fact that random k-SAT has a "hard" distribution of solutions does not seem to be relevant for proving a time lower bound on k-SAT. It is not sufficient to use a problem with a hard distribution of solutions, if you're separating P from NP. This is the objection which seems most germane to the current proposed proof: it opposes the claim that "anything in P can't have a solution space with this intriguing structure". It appears there must be some error in either the translation to this logic, or the analysis of solution spaces that this logic permits.
## Moreover, it's also worth pointing out that a hard distribution of solutions is not ''necessary'' for NP-hardness, either. A weird distribution is ''not'' what makes a problem hard, it's the representation of that solution space (e.g., a 3-CNF formula, a 2-CNF formula, etc.). The "hard" case of 3-SAT is the case where there is ''at most one'' satisfying assignment, since there is a randomized reduction from 3-SAT to 3-SAT with at most one satisfying assignment ([http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem Valiant-Vazirani]). This reduction increases the number of clauses and the number of variables, but that doesn't really matter. The point is that you can always reduce 3-SAT with a "complex" solution space to one with an "easy" solution space, so how can a proof separating P from NP rely on the former? (Note that, if plausible circuit lower bounds hold up, then Valiant-Vazirani can be derandomized to run in deterministic polynomial time.) To summarize, there is essentially no correlation between the "hard structure" of the solution space for instances of some problem, and the NP-hardness of that problem.

=== Barriers ===

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

==== Relativization ====

Quick overview of Relativization Barrier at [http://kintali.wordpress.com/2009/09/01/relativization-barrier/ Shiva Kintali's blog post]

==== Natural proofs ====

See Razborov and Rudich, "[http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf Natural proofs]" ''Proceedings of the twenty-sixth annual ACM symposium on Theory of computing'' (1994).

(Some discussion on the uniformity vs. non-uniformity distinction seems relevant here; the current strategy does not, strictly speaking, trigger this barrier so long as it exploits uniformity in an essential way.)

==== Algebrization ====

See Aaronson and Widgerson, "[http://www.scottaaronson.com/papers/alg.pdf Algebrization: A New Barrier in Complexity Theory]" ''ACM Transactions on Computation Theory'' (2009).

:The paper is all about the local properties of a specific NP-complete problem (k-SAT), and for that reason, I don't think relativization is relevant. Personally, I'm more interested in why the argument makes essential use of uniformity (which is apparently why it's supposed to avoid Razborov-Rudich). ([http://scottaaronson.com/blog/?p=456#comment-44649 Scott Aaronson])

==== Average to Worst-case?====
A possible new barrier implied by the discussion here, framed by [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np#comment-4885 Terry Tao]:
<blockquote>
If nothing else, this whole experience has highlighted a “philosophical” barrier to P != NP which is distinct from the three “hard” barriers of relativisation, natural proofs, and algebraisation, namely the difficulty in using average-case (or “global”) behaviour to separate worst-case complexity, due to the existence of basic problems (e.g. k-SAT and k-XORSAT) which are expected to have similar average case behaviour in many ways, but completely different worst case behaviour. (I guess this difficulty was well known to the experts, but it is probably good to make it more explicit.)
</blockquote>
Followup by Ryan Williams:
<blockquote>
It is a great idea to try to formally define this barrier and develop its properties. I think the “not necessary” part is pretty well-understood, thanks to Valiant-Vazirani. But the “not sufficient” part, the part relevant to the current paper under discussion, still needs some more rigor behind it. As I related to Lenka Zdeborova, it is easy to construct, for every n, a 2-CNF formula on n variables which has many “clusters” of solutions, where each cluster has large hamming distance from each other, and within the cluster there are a lot of satisfying assignments. But one would like to say something stronger, e.g. “for any 3-CNF formula with solution space S, that space S can be very closely simulated by the solution space S’ for some CSP instance variables that is polytime solvable”.
</blockquote>

== Terminology ==

* [http://en.wikipedia.org/wiki/Boolean_satisfiability_problem Boolean satisfiability problem] (SAT)
* [http://en.wikipedia.org/wiki/Finite_model_theory Finite model theory]
* [[Immerman-Vardi theorem]]
* [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]]
* [[The complexity class NP]]
* [[The complexity class P]]

== Online reactions ==

=== Theoretical computer science blogs ===

* [http://gregbaker.ca/blog/author/greg/ P ≠ NP], Greg Baker, Greg and Kat’s blog, August 7 2010.
* [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ A proof that P is not equal to NP?], Richard Lipton, Gödel’s lost letter and P=NP, August 8 2010.
* [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html On the Deolalikar proof: Crowdsourcing the discussion ?], Suresh Venkatasubramanian, The Geomblog, August 9 2010.
* [http://scottaaronson.com/blog/?p=456 Putting my money where my mouth isn’t], Scott Aaronson, Shtetl-Optimized, August 9 2010.
* [http://blog.computationalcomplexity.org/2010/08/that-p-ne-np-proof-whats-up-with-that.html That P ne NP proof- whats up with that?], Bill Gasarch, Computational Complexity, August 9 2010.
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ Issues In The Proof That P≠NP], Richard Lipton and Ken Regan, Gödel’s lost letter and P=NP, August 9 2010.
* [http://constraints.wordpress.com/2010/08/09/deolalikars-manuscript/ Deolalikar's manuscript], András Salamon, Constraints, August 9 2010.
* [http://aeporreca.org/2010/08/09/proof-that-p-isnt-np/ A relatively serious proof that P != NP ?], Antonio E. Porreca, August 9 2010 (aggregated many of the comments).
* [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html A 'polymath' home for analysis of the Deolalikar proof], Suresh Venkatasubramanian, The Geomblog, August 10 2010.
* [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/ Update on Deolalikar's Proof that P≠NP], Richard Lipton and Ken Regan, Gödel’s lost letter and P=NP, August 10 2010.
* [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/ Deolalikar Responds To Issues About His P≠NP Proof] Gödel’s lost letter and P=NP, August 11, 2010
* [http://scottaaronson.com/blog/?p=457 The ethics of scientific betting], Scott Aaronson, Shtetl-Optimized, August 11 2010.
* [http://geomblog.blogspot.com/2010/08/p-vs-np-what-ive-learnt-so-far.html P vs NP: What I've learnt so far...], Suresh Venkatasubramanian, The Geomblog, August 11 2010.

=== Media and aggregators ===

====8th August====
* [http://news.ycombinator.com/item?id=1585850 P ≠ NP], Hacker News, August 8 2010.
* [http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP Claimed Proof That P != NP], Slashdot, August 8 2010.
* [http://www.heise.de/newsticker/meldung/P-NP-moeglicherweise-bewiesen-1052857.html P != NP möglicherweise bewiesen], heise online, August 8 2010.

====9th August====

* [http://www.aolnews.com/surge-desk/article/p-np-wtf-a-short-guide-to-understanding-vinay-deolalikars-mat/19586401 P=NP=WTF?: A Short Guide to Understanding Vinay Deolalikar's Mathematical Breakthrough], Dana Chivvis, AolNews, August 9 2010.
* [http://www.pcworld.com/article/202950/hp_researcher_claims_to_crack_compsci_complexity_conundrum.html HP Researcher Claims to Crack Compsci Complexity Conundrum], Joab Jackson, IDG News, August 9 2010.

====10th August====

* [http://www.nature.com/news/2010/100810/full/news.2010.398.html Million-dollar problem cracked?] Geoff Brumfiel, nature news, August 10 2010.
* [http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html P ≠ NP? It's bad news for the power of computing] Richard Elwes, New Scientist, August 10 2010.
* [http://blogs.forbes.com/leegomes/2010/08/10/the-non-flaming-of-an-hp-mathematician/?boxes=Homepagechannels The Non-Flaming of an HP Mathematician], Lee Gomes, Forbes, August 10 2010.
* [http://blogs.discovermagazine.com/80beats/2010/08/10/has-the-devilish-math-problem-p-vs-np-finally-been-solved/ Has the Devilish Math Problem “P vs NP” Finally Been Solved?], Andrew Moseman, 80 beats, Discover blogs, August 10 2010.

====11th August====

* [http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP], Alastair Jamieson, The Daily Telegraph, August 11 2010.
* [http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof Possible issues with the P!=NP proof], Slashdot, August 11 2010.
* [http://www.bbc.co.uk/news/science-environment-10938302 Million dollar maths puzzle sparks row], Victoria Gill, BBC News, August 11 2010.
* [http://www.infoworld.com/t/code-analysis/computer-science-breakthrough-the-end-p-np-583 Computer science breakthrough: The end of P = NP?], Woody Leonhard, InfoWorld, August 11 2010.
* [http://www.wired.co.uk/news/archive/2010-08/11/p-vs-np-solved Proof offered for P vs NP mathematical puzzle], Duncan Geere, Wired.co.uk, August 11 2010.
* [http://blogs.forbes.com/leegomes/2010/08/11/a-beautiful-sausage/ A beautiful sausage], Lee Gomes, Forbes, August 11 2010.

=== Real-time searches ===

* [http://search.twitter.com/search?q=P%20NP Current Twitter search for "P NP"]
* [http://twitter.com/search?q=Deolalikar Current Twitter search for "Deolalikar"]
* [http://news.google.com/news/search?aq=f&pz=1&cf=all&ned=us&hl=en&q=P+NP Current Google News search for "P NP"]

=== Other ===

* [http://twitter.com/fortnow/statuses/20673954168 Twitter], Lance Fortnow, August 8 2010.
* [http://dabacon.org/pontiff/?p=4286 P<>NP?], Dave Bacon, The Quantum Pontiff, August 8 2010.
* [http://www.daniel-lemire.com/blog/archives/2010/08/09/how-to-get-everyone-talking-about-your-research/ How to get everyone talking about your research], Daniel Lemire, August 9 2010.
* [http://twitter.com/rrwilliams/status/20741046788 Twitter], Ryan Williams, August 9 2010.
* [http://www.google.com/buzz/114134834346472219368/1vfSCPtRQZf/Vinay-Deolaikar-recently-released-a-102-page Google Buzz], Terence Tao, August 9 2010.
* [http://www.schneier.com/blog/archives/2010/08/p_np_1.html P ≠ NP?], Bruce Schneier, Schneier on Security, August 9 2010.
* [http://blog.vixra.org/2010/08/09/vinay-deolalikar-says-p-%E2%89%A0-np/ Vinay Deolalikar says P ≠ NP], Philip Gibbs, vixra log, August 9 2010.
* [http://dabacon.org/pontiff/?p=4292 P<>NP Hype], Dave Bacon, The Quantum Pontiff, August 10 2010.
* [http://cameronneylon.net/blog/p-%E2%89%A0-np-and-the-future-of-peer-review/ P ≠ NP and the future of peer review] Cameron Neylon, Science in the Open, August 10 2010.
* [http://computacioncuantica.blogspot.com/2010/08/una-prueba-de-que-p-np.html Una prueba de que P≠NP? (Spanish)], Alejandro Díaz-Caro, Computación Cuántica, Aug 10 2010.
* [http://gowers.wordpress.com/2010/08/11/my-pennyworth-about-deolalikar/ My pennyworth about Deolalikar], Tim Gowers, Aug 11 2010.
* [http://blog.oddhead.com/2010/08/11/betting-on-p-equals-np/ Where is the betting market for P=NP when you need it?], David Pennock, Oddhead Blog, August 11 2010

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

== Timeline ==

* August 6: Vinay Deolalikar sends out [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf his manuscript] to several experts in the field.
* August 7: Greg Baker [http://gregbaker.ca/blog/2010/08/07/p-n-np/ posts about the manuscript on his blog].
* August 8: The paper is noted on [http://news.ycombinator.com/item?id=1585850 Hacker News] and [http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP Slashdot], and [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P%21%3DNP_paper#Theory_blogs discussed on many theoretical computer science blogs].
* August 9: A [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf second draft of the manuscript] is posted.
* August 9: Suresh Venkatasubramanian [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html collects several technical comments on the paper] into a [https://docs.google.com/document/edit?id=1uOa3BE7oK8Q7iEuOZ1EfkS16lF_Um1VwyMgdzrjZuT0&hl=en&authkey=COS65rkE collaborative document].
* August 9: [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ 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 [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html is migrated over] to a [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper wiki page].
* August 10: The paper, and all mention of it, is removed from Deolalikar's [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ home page], but can be found in his [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/ "Papers" subdirectory].
* August 11: A [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf third draft] of the paper reappears on Deolalikar's [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ home page].

== Bibliography ==

* [AVV1997] S. Abiteboul, M. Y. Yardi, V. Vianu, "[http://portal.acm.org/citation.cfm?id=256295 Fixpoint logics, relational machines, and computational complexity]", Journal of the ACM (JACM) Volume 44, Issue 1 (January 1997), 30-56.
* [AM2003] D. Achlioptas, C. Moore, "[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 Almost all graphs with average degree 4 are 3-colorable]", Journal of Computer and System Sciences 67, Issue 2, September 2003, 441-471.
* [I1986] N. Immerman, "[http://www.cs.umass.edu/~immerman/pub/query.pdf Relational queries computable in polynomial time]", Information and Control 68 (1986), 86-104.
* [VV1986] L. G. Valiant, V. V. Vazirani, "[http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf 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, "[http://www.dcc.uchile.cl/~cgutierr/cursos/CC/vardi-complex-bd.pdf Complexity of Relational Query Languages]", 14th Symposium on Theory of Computation (1982), 137-146.

== Other links ==

* [http://en.wikipedia.org/wiki/Vinay_Deolalikar Vinay Deolalikar] - Wikipedia
* [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/d/Deolalikar:Vinay.html Deolalikar publication list] - DBLP
* [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Gerhard Woeginger’s P-versus-NP page]
* A nice introductory [http://www.ugcs.caltech.edu/~stansife/pnp.html Q&A page] on Deolalikar's proof, by Eric Stansifer.

== Further reading ==

Given the current interest in the subject matters discussed on this page, it would be good to start collecting a list of references where people can learn more about such topics. Please add liberally to the list below.

* [http://en.wikipedia.org/wiki/P_%3D_NP_problem P versus NP problem] - Wikipedia
* [http://www.win.tue.nl/~gwoegi/P-versus-NP/sipser.pdf The History and Status of the P Versus NP Question], Michael Sipser 1992
* [http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf The Status of the P versus NP Problem], Lance Fortnow 2009
* [http://kintali.wordpress.com/2009/09/01/relativization-barrier/ Relativization Barrier]
* [http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams P=NP, relativisation, and multiple choice exams], Terence Tao

* There are many other complexity classes besides P and NP. See the [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]

* P=NP? is discrete mathematics. Similar questions can be asked over other domains: P=NP over R? See [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4678&rep=rep1&type=pdf Complexity Theory and Numerical Analysis], Steve Smale, 2000

* Complexity classes for particular subjects have been investigated, e.g. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.4877&rep=rep1&type=pdf Open problems in number theoretic complexity, II], L Adleman, K McCurley - Algorithmic Number Theory, 1994

* [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=38D2317557C5EF25F3ED6D0D3CBE6E69?doi=10.1.1.28.6917&rep=rep1&type=pdf Finite Model Theory - A Personal Perspective], Ronald Fagin 1993
* [http://www.logic.rwth-aachen.de/pub/graedel/FMTbook-Chapter3.pdf Finite Model Theory and Descriptive Complexity] - Erich Grädel.

* Here is a [http://wiki.henryfarrell.net/wiki/index.php/Computer_Science list of blogs in computer science] (including several blogs who have been actively posting on this topic).

Deolalikar P vs NP paper

2010-08-12T04:01:55Z

MciprianM:

This is a clearinghouse wiki page for aggregating the following types of items:

# Analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP;
# News and information about this preprint;
# Background material for the various concepts used in the preprint; and
# Evaluation of the feasibility and limitations of the general strategies used to attack P != NP, including those in the preprint.

It is hosted by the [[Main Page|polymath project wiki]], but is not a formal polymath project.

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 [https://docs.google.com/document/edit?id=1uOa3BE7oK8Q7iEuOZ1EfkS16lF_Um1VwyMgdzrjZuT0&hl=en&authkey=COS65rkE earlier collaborative document] [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html created by Suresh Venkatasubramanian].

== Discussion threads ==

The main discussion threads are being hosted on Dick Lipton's blog. Several of the posts were written jointly with Ken Regan.

* [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ A proof that P is not equal to NP?], August 8 2010. (Inactive)
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ Issues In The Proof That P≠NP], August 9 2010. (Inactive)
* [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/ Update on Deolalikar's Proof that P≠NP], August 10 2010. (Inactive)
* [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/ Deolalikar Responds To Issues About His P≠NP Proof] August 11, 2010 ('''Active''')

== The paper ==

These links are taken from [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ Vinay Deolalikar's web page].

* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf First draft], Aug 6, 2010
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf Second draft] Aug 9, 2010. '''File removed,''' Aug 10 2010.
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated-mjr.pdf draft 2 + ε], Aug 9 2010. '''File removed,''' ( Aug 12? 2010 )
* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf Third draft], Aug 11 2010.

Here is the list of [[Update|updates]] between the different versions.

== Typos and minor errors ==

Any typos appearing in an earlier draft that no longer appear in the latest draft should be struck out.

* <strike>(Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via [http://scottaaronson.com/blog/?p=456#comment-44783 Blake Stacey])</strike>
* (Second draft) Some (but not all) of the instances of the <math>O()</math> notation should probably be <math>\Theta()</math> or <math>\Omega()</math> instead, e.g. on pages 4, 9, 16, 28, 33, 57, 68, etc. (via [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4530 András Salamon])
** Still present in the third draft, e.g. "O(n) Hamming separation between clusters" occurs on page 68 and similarly in several other places.
* (Second draft, page 27) <math>n 2^n</math> independent parameters → <math> n 2^k</math> independent parameters
* (draft 2 + e, p.34, Def. 3.8): <math>n</math> → <math>k</math>
* (Second draft, page 52) <math>\sum C_{li}S_i-k>0</math> → <math>\sum C_{li}S_i+k>0 </math>
* (draft 2 + e, p.10): "We reproduce the rigorously proved picture of the 1RSB ansatz that we will need in Chapter 5." The phrasing makes it sound like we will need the 1RSB ansatz in Chapter 5 instead of saying that it is reproduced in Chapter 5 (which I think is what the author intended). One fix is to move "in Chapter 5" to the beginning of the sentence.
* (Third draft, p. 102): "inspite" → "in spite"

== Proof strategy ==

(Excerpted from [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4491 this comment of Ken Regan])

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

# 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.
# All P-queries over V can be expressed by FO(LFP) formulas over V.
# NP = P implies Q is expressible by an FO(LFP) formula over V.
# 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.
# Such an algorithm, however, contradicts known statistical properties of randomized k-SAT when k >= 9.

===An alternate perspective===
[http://scottaaronson.com/blog/?p=456#comment-44844 Leonid Gurvits]:
<blockquote>
...the discrete probabilistic distributions in the paper can be viewed
as tensors, or very special multilinear polynomials.
The assumptions “P=NP” somehow gives a (polynomial?)
upper bound on the tensor rank. And finally, using
known probabilistic results, he gets nonmatching
(exponential?) lower bound on the same rank.

If I am right, then this approach is a very clever, in a good sense
elementary, way to push the previous algebraic-geometric approaches.
</blockquote>

== Possible issues ==

=== Issues with LFP ===

[http://www.logic.rwth-aachen.de/~graedel/ Erich Grädel] has an [http://www.logic.rwth-aachen.de/pub/graedel/FMTbook-Chapter3.pdf extensive review of finite model theory and descriptive complexity].

There appear to be 4 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 [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ Lipton/Regan post], with contributions from David Barrington, Paul Christiano, Lance Fortnow, James Gate, Arthur Milchior, Charanjit Jutla, Julian Bradfield and Steven Lindell.

* Is the lack of ordering in the logical structures used to define the LFP structure a problem (since parity can not be expressed without an ordering even with LFP, hence P is not captured without order).
::In chapter 7 this issue seems to disappear since he introduces a successor relation over the variables <math>x_1<\dots<x_n<\neg x_1<\dots<\neg x_n</math>.
:: If it was possible to express k-SAT in FO(NLFP,without succ) (NLFP=non deterministic LFP) or in relational-NP, as introduced in [[http://portal.acm.org/citation.cfm?id=256295 AVV1997]] then by an extension of the Abiteboul-Vianu theorem it would be enough to prove that k-SAT is not in FO(LFP,without succ). This would avoid the problem of the order
* '''The issue of tupling''': 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.
::[http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np#comment-4828 Albert Atserias says], "...for someone knowing the finite model theory used in the paper, there is a jump in the reasoning that lacks justification. This is the jump from Monadic LFP to full LFP. The only justification for this crucial step seems to be Remark 7.4 in page 70 of the original manuscript (and the vague statement in point 3 of page 49), but this is far from satisfactory. The standard constructions of the so-called canonical structures that Vinay refers to (see Ebbinghaus and Flum book in page 54) have a Gaifman graph of constant diameter, even without the linear order, due to the generalized equalities that allow the decoding of tuples into its components. Issues along these lines were raised before [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/#comment-4677 here] and [http://scottaaronson.com/blog/?p=456#comments in comment 54 here]
::[http://www.haverford.edu/cmsc/slindell/ Steven Lindell] presents a [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4898 detailed critique of this problem], with an indication that there might be insurmountable problems. It is reproduced [[Lindell's Critique | here]] for completeness.
* Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4737 Charanjit Jutla] has pointed out that the argument in section 4.3 (with which several other people have also had issues) depends on the absence of a greatest fixed point. "This is a usual mistake most people new to fixed-point logics fall prey to. For example, now he has to deal with formulas of the kind <math>\nu x (f(y, x) \and g(y, x)).</math> Section 4.2 deals with just one least fixed point operator…where his idea is correct. But, in the next section 4.3, where he deals with complex fixed point iterations, he is just '''hand waving''', and possibly '''way off'''."
:: A few comments later, [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4801 he appears to revise this objection], while bringing up a new issue about the boundedness of the universe relating to the LFP operator.

=== Issues with phase transitions ===

''A brief synopsis of the terms discussed can be found [[Random_k-SAT|here]]''

# '''The nomenclature of phase transitions''': In the statistical physics picture, there is not a single phase transition, but rather a set of different well defined transitions called '''clustering (equivalently d1RSB)''', '''condensation''', and '''freezing''' ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4723 Florent Krzakala] and [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4633 Lenka Zdeborova]). In the current version of the paper, properties of d1RSB (clustering), and freezing are mixed-up. Whereas following the established definitions, and contrary to some earlier conjectures, it is now agreed that some polynomial algorithms work beyond the d1RSB (clustering) or condensation thresholds. Graph coloring provides some evidence of this when one [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 compares the performance of algorithms] with the [http://arxiv.org/abs/0704.1269 statistical physics predictions.] The property of the solution space of random K-SAT the paper is actually using is called freezing. It was [http://arxiv.org/abs/0704.1269 conjectured] in the statistical physics community ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4723 Florent Krzakala], [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4633 Lenka Zdeborova] and [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/#comment-4661 Cris Moore]) that really hard instances appears in the frozen phase, i.e. when all solutions have non-trivial cores. Existence of such a region was proven rigorously by Achlioptas and Ricci-Tersenghi and their theorem appears as Theorem 5.1 in the paper.
# '''The XOR-SAT objection ''': The conjecture that frozen variables make a problem hard is however restricted to NP-complete problems such as K-SAT and Q-COL. Indeed a linear problem such as random k-XORSAT also has a clustering transition, frozen variables, etc., and is not easy to solve with most algorithms, but is of course in P as one can use Gauss elimination and exploit the linear structure to solve it in polynomial time ([http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4505 Cris Moore], [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np#comment-4518 Alif Wahid], and [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/#comment-4633 Lenka Zdeborova]). Similar problem might exists in other restricted CSP which are in P, but may exibit freezing stage, as pointed by several other people.
# '''The error-correcting codes objection''': Initiated in a [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4839 comment by harrison]: If I understand his argument correctly, Deolalikar claims that the polylog-conditional independence means that the solution space of a poly-time computation can’t have Hamming distance O(n) [presumably he means \theta(n)], as long as there are “sufficiently many solution clusters.” This would preclude the existence of efficiently decodable codes at anything near the Gilbert-Varshamov bound when the minimum Hamming distance is large enough.

===Issues with random k-SAT===
# '''Complex solution spaces are uncorrelated with time complexity'''. (The below is a greatly expanded version of a series of twitter comments by Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]) The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". For certain parameterizations, the space of satisfying assignments to a random k-SAT instance has some intriguing structure. If SAT is in P, then SAT can be captured in a certain logic (equivalent to P in some sense). The author claims that anything captured in this logic can't have a solution space with this intriguing structure. There are two "meta" objections to this. One is that "intriguing structure in the solution space is not sufficient for NP hardness". The second is that "intriguing structure is not necessary for NP hardness". They don't actually point to a place where the proof is wrong. But they do appear to give an obstacle to the general proof method.
## Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions. In fact it is not hard to design 2-SAT formulas (in this case not random, but specifically designed ones) so that they have exponentially many clusters of solutions, each cluster being "far" from the others, etc. That is, the fact that random k-SAT has a "hard" distribution of solutions does not seem to be relevant for proving a time lower bound on k-SAT. It is not sufficient to use a problem with a hard distribution of solutions, if you're separating P from NP. This is the objection which seems most germane to the current proposed proof: it opposes the claim that "anything in P can't have a solution space with this intriguing structure". It appears there must be some error in either the translation to this logic, or the analysis of solution spaces that this logic permits.
## Moreover, it's also worth pointing out that a hard distribution of solutions is not ''necessary'' for NP-hardness, either. A weird distribution is ''not'' what makes a problem hard, it's the representation of that solution space (e.g., a 3-CNF formula, a 2-CNF formula, etc.). The "hard" case of 3-SAT is the case where there is ''at most one'' satisfying assignment, since there is a randomized reduction from 3-SAT to 3-SAT with at most one satisfying assignment ([http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem Valiant-Vazirani]). This reduction increases the number of clauses and the number of variables, but that doesn't really matter. The point is that you can always reduce 3-SAT with a "complex" solution space to one with an "easy" solution space, so how can a proof separating P from NP rely on the former? (Note that, if plausible circuit lower bounds hold up, then Valiant-Vazirani can be derandomized to run in deterministic polynomial time.) To summarize, there is essentially no correlation between the "hard structure" of the solution space for instances of some problem, and the NP-hardness of that problem.

=== Barriers ===

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

==== Relativization ====

Quick overview of Relativization Barrier at [http://kintali.wordpress.com/2009/09/01/relativization-barrier/ Shiva Kintali's blog post]

==== Natural proofs ====

See Razborov and Rudich, "[http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf Natural proofs]" ''Proceedings of the twenty-sixth annual ACM symposium on Theory of computing'' (1994).

(Some discussion on the uniformity vs. non-uniformity distinction seems relevant here; the current strategy does not, strictly speaking, trigger this barrier so long as it exploits uniformity in an essential way.)

==== Algebrization ====

See Aaronson and Widgerson, "[http://www.scottaaronson.com/papers/alg.pdf Algebrization: A New Barrier in Complexity Theory]" ''ACM Transactions on Computation Theory'' (2009).

:The paper is all about the local properties of a specific NP-complete problem (k-SAT), and for that reason, I don't think relativization is relevant. Personally, I'm more interested in why the argument makes essential use of uniformity (which is apparently why it's supposed to avoid Razborov-Rudich). ([http://scottaaronson.com/blog/?p=456#comment-44649 Scott Aaronson])

==== Average to Worst-case?====
A possible new barrier implied by the discussion here, framed by [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np#comment-4885 Terry Tao]:
<blockquote>
If nothing else, this whole experience has highlighted a “philosophical” barrier to P != NP which is distinct from the three “hard” barriers of relativisation, natural proofs, and algebraisation, namely the difficulty in using average-case (or “global”) behaviour to separate worst-case complexity, due to the existence of basic problems (e.g. k-SAT and k-XORSAT) which are expected to have similar average case behaviour in many ways, but completely different worst case behaviour. (I guess this difficulty was well known to the experts, but it is probably good to make it more explicit.)
</blockquote>

== Terminology ==

* [http://en.wikipedia.org/wiki/Boolean_satisfiability_problem Boolean satisfiability problem] (SAT)
* [http://en.wikipedia.org/wiki/Finite_model_theory Finite model theory]
* [[Immerman-Vardi theorem]]
* [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]]
* [[The complexity class NP]]
* [[The complexity class P]]

== Online reactions ==

=== Theoretical computer science blogs ===

* [http://gregbaker.ca/blog/author/greg/ P ≠ NP], Greg Baker, Greg and Kat’s blog, August 7 2010.
* [http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ A proof that P is not equal to NP?], Richard Lipton, Gödel’s lost letter and P=NP, August 8 2010.
* [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html On the Deolalikar proof: Crowdsourcing the discussion ?], Suresh Venkatasubramanian, The Geomblog, August 9 2010.
* [http://scottaaronson.com/blog/?p=456 Putting my money where my mouth isn’t], Scott Aaronson, Shtetl-Optimized, August 9 2010.
* [http://blog.computationalcomplexity.org/2010/08/that-p-ne-np-proof-whats-up-with-that.html That P ne NP proof- whats up with that?], Bill Gasarch, Computational Complexity, August 9 2010.
* [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ Issues In The Proof That P≠NP], Richard Lipton and Ken Regan, Gödel’s lost letter and P=NP, August 9 2010.
* [http://constraints.wordpress.com/2010/08/09/deolalikars-manuscript/ Deolalikar's manuscript], András Salamon, Constraints, August 9 2010.
* [http://aeporreca.org/2010/08/09/proof-that-p-isnt-np/ A relatively serious proof that P != NP ?], Antonio E. Porreca, August 9 2010 (aggregated many of the comments).
* [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html A 'polymath' home for analysis of the Deolalikar proof], Suresh Venkatasubramanian, The Geomblog, August 10 2010.
* [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/ Update on Deolalikar's Proof that P≠NP], Richard Lipton and Ken Regan, Gödel’s lost letter and P=NP, August 10 2010.
* [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/ Deolalikar Responds To Issues About His P≠NP Proof] Gödel’s lost letter and P=NP, August 11, 2010
* [http://scottaaronson.com/blog/?p=457 The ethics of scientific betting], Scott Aaronson, Shtetl-Optimized, August 11 2010.
* [http://geomblog.blogspot.com/2010/08/p-vs-np-what-ive-learnt-so-far.html P vs NP: What I've learnt so far...], Suresh Venkatasubramanian, The Geomblog, August 11 2010.

=== Media and aggregators ===

====8th August====
* [http://news.ycombinator.com/item?id=1585850 P ≠ NP], Hacker News, August 8 2010.
* [http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP Claimed Proof That P != NP], Slashdot, August 8 2010.
* [http://www.heise.de/newsticker/meldung/P-NP-moeglicherweise-bewiesen-1052857.html P != NP möglicherweise bewiesen], heise online, August 8 2010.

====9th August====

* [http://www.aolnews.com/surge-desk/article/p-np-wtf-a-short-guide-to-understanding-vinay-deolalikars-mat/19586401 P=NP=WTF?: A Short Guide to Understanding Vinay Deolalikar's Mathematical Breakthrough], Dana Chivvis, AolNews, August 9 2010.
* [http://www.pcworld.com/article/202950/hp_researcher_claims_to_crack_compsci_complexity_conundrum.html HP Researcher Claims to Crack Compsci Complexity Conundrum], Joab Jackson, IDG News, August 9 2010.

====10th August====

* [http://www.nature.com/news/2010/100810/full/news.2010.398.html Million-dollar problem cracked?] Geoff Brumfiel, nature news, August 10 2010.
* [http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html P ≠ NP? It's bad news for the power of computing] Richard Elwes, New Scientist, August 10 2010.
* [http://blogs.forbes.com/leegomes/2010/08/10/the-non-flaming-of-an-hp-mathematician/?boxes=Homepagechannels The Non-Flaming of an HP Mathematician], Lee Gomes, Forbes, August 10 2010.
* [http://blogs.discovermagazine.com/80beats/2010/08/10/has-the-devilish-math-problem-p-vs-np-finally-been-solved/ Has the Devilish Math Problem “P vs NP” Finally Been Solved?], Andrew Moseman, 80 beats, Discover blogs, August 10 2010.

====11th August====

* [http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html Computer scientist Vinay Deolalikar claims to have solved maths riddle of P vs NP], Alastair Jamieson, The Daily Telegraph, August 11 2010.
* [http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof Possible issues with the P!=NP proof], Slashdot, August 11 2010.
* [http://www.bbc.co.uk/news/science-environment-10938302 Million dollar maths puzzle sparks row], Victoria Gill, BBC News, August 11 2010.
* [http://www.infoworld.com/t/code-analysis/computer-science-breakthrough-the-end-p-np-583 Computer science breakthrough: The end of P = NP?], Woody Leonhard, InfoWorld, August 11 2010.
* [http://www.wired.co.uk/news/archive/2010-08/11/p-vs-np-solved Proof offered for P vs NP mathematical puzzle], Duncan Geere, Wired.co.uk, August 11 2010.
* [http://blogs.forbes.com/leegomes/2010/08/11/a-beautiful-sausage/ A beautiful sausage], Lee Gomes, Forbes, August 11 2010.

=== Real-time searches ===

* [http://search.twitter.com/search?q=P%20NP Current Twitter search for "P NP"]
* [http://twitter.com/search?q=Deolalikar Current Twitter search for "Deolalikar"]
* [http://news.google.com/news/search?aq=f&pz=1&cf=all&ned=us&hl=en&q=P+NP Current Google News search for "P NP"]

=== Other ===

* [http://twitter.com/fortnow/statuses/20673954168 Twitter], Lance Fortnow, August 8 2010.
* [http://dabacon.org/pontiff/?p=4286 P<>NP?], Dave Bacon, The Quantum Pontiff, August 8 2010.
* [http://www.daniel-lemire.com/blog/archives/2010/08/09/how-to-get-everyone-talking-about-your-research/ How to get everyone talking about your research], Daniel Lemire, August 9 2010.
* [http://twitter.com/rrwilliams/status/20741046788 Twitter], Ryan Williams, August 9 2010.
* [http://www.google.com/buzz/114134834346472219368/1vfSCPtRQZf/Vinay-Deolaikar-recently-released-a-102-page Google Buzz], Terence Tao, August 9 2010.
* [http://www.schneier.com/blog/archives/2010/08/p_np_1.html P ≠ NP?], Bruce Schneier, Schneier on Security, August 9 2010.
* [http://blog.vixra.org/2010/08/09/vinay-deolalikar-says-p-%E2%89%A0-np/ Vinay Deolalikar says P ≠ NP], Philip Gibbs, vixra log, August 9 2010.
* [http://dabacon.org/pontiff/?p=4292 P<>NP Hype], Dave Bacon, The Quantum Pontiff, August 10 2010.
* [http://cameronneylon.net/blog/p-%E2%89%A0-np-and-the-future-of-peer-review/ P ≠ NP and the future of peer review] Cameron Neylon, Science in the Open, August 10 2010.
* [http://computacioncuantica.blogspot.com/2010/08/una-prueba-de-que-p-np.html Una prueba de que P≠NP? (Spanish)], Alejandro Díaz-Caro, Computación Cuántica, Aug 10 2010.
* [http://gowers.wordpress.com/2010/08/11/my-pennyworth-about-deolalikar/ My pennyworth about Deolalikar], Tim Gowers, Aug 11 2010.
* [http://blog.oddhead.com/2010/08/11/betting-on-p-equals-np/ Where is the betting market for P=NP when you need it?], David Pennock, Oddhead Blog, August 11 2010

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

== Timeline ==

* August 6: Vinay Deolalikar sends out [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf his manuscript] to several experts in the field.
* August 7: Greg Baker [http://gregbaker.ca/blog/2010/08/07/p-n-np/ posts about the manuscript on his blog].
* August 8: The paper is noted on [http://news.ycombinator.com/item?id=1585850 Hacker News] and [http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP Slashdot], and [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar%27s_P%21%3DNP_paper#Theory_blogs discussed on many theoretical computer science blogs].
* August 9: A [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated.pdf second draft of the manuscript] is posted.
* August 9: Suresh Venkatasubramanian [http://geomblog.blogspot.com/2010/08/on-deolalikar-proof-crowdsourcing.html collects several technical comments on the paper] into a [https://docs.google.com/document/edit?id=1uOa3BE7oK8Q7iEuOZ1EfkS16lF_Um1VwyMgdzrjZuT0&hl=en&authkey=COS65rkE collaborative document].
* August 9: [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/ 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 [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html is migrated over] to a [http://michaelnielsen.org/polymath1/index.php?title=Deolalikar's_P!%3DNP_paper wiki page].
* August 10: The paper, and all mention of it, is removed from Deolalikar's [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ home page], but can be found in his [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/ "Papers" subdirectory].
* August 11: A [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf third draft] of the paper reappears on Deolalikar's [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ home page].

== Bibliography ==

* [AVV1997] S. Abiteboul, M. Y. Yardi, V. Vianu, "[http://portal.acm.org/citation.cfm?id=256295 Fixpoint logics, relational machines, and computational complexity]", Journal of the ACM (JACM) Volume 44, Issue 1 (January 1997), 30-56.
* [AM2003] D. Achlioptas, C. Moore, "[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 Almost all graphs with average degree 4 are 3-colorable]", Journal of Computer and System Sciences 67, Issue 2, September 2003, 441-471.
* [I1986] N. Immerman, "[http://www.cs.umass.edu/~immerman/pub/query.pdf Relational queries computable in polynomial time]", Information and Control 68 (1986), 86-104.
* [VV1986] L. G. Valiant, V. V. Vazirani, "[http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf 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, "[http://www.dcc.uchile.cl/~cgutierr/cursos/CC/vardi-complex-bd.pdf Complexity of Relational Query Languages]", 14th Symposium on Theory of Computation (1982), 137-146.

== Other links ==

* [http://en.wikipedia.org/wiki/Vinay_Deolalikar Vinay Deolalikar] - Wikipedia
* [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/d/Deolalikar:Vinay.html Deolalikar publication list] - DBLP
* [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Gerhard Woeginger’s P-versus-NP page]
* A nice introductory [http://www.ugcs.caltech.edu/~stansife/pnp.html Q&A page] on Deolalikar's proof, by Eric Stansifer.

== Further reading ==

Given the current interest in the subject matters discussed on this page, it would be good to start collecting a list of references where people can learn more about such topics. Please add liberally to the list below.

* [http://en.wikipedia.org/wiki/P_%3D_NP_problem P versus NP problem] - Wikipedia
* [http://www.win.tue.nl/~gwoegi/P-versus-NP/sipser.pdf The History and Status of the P Versus NP Question], Michael Sipser 1992
* [http://people.cs.uchicago.edu/~fortnow/papers/pnp-cacm.pdf The Status of the P versus NP Problem], Lance Fortnow 2009
* [http://kintali.wordpress.com/2009/09/01/relativization-barrier/ Relativization Barrier]
* [http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams P=NP, relativisation, and multiple choice exams], Terence Tao

* There are many other complexity classes besides P and NP. See the [http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity Zoo]

* P=NP? is discrete mathematics. Similar questions can be asked over other domains: P=NP over R? See [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4678&rep=rep1&type=pdf Complexity Theory and Numerical Analysis], Steve Smale, 2000

* Complexity classes for particular subjects have been investigated, e.g. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.4877&rep=rep1&type=pdf Open problems in number theoretic complexity, II], L Adleman, K McCurley - Algorithmic Number Theory, 1994

* [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=38D2317557C5EF25F3ED6D0D3CBE6E69?doi=10.1.1.28.6917&rep=rep1&type=pdf Finite Model Theory - A Personal Perspective], Ronald Fagin 1993
* [http://www.logic.rwth-aachen.de/pub/graedel/FMTbook-Chapter3.pdf Finite Model Theory and Descriptive Complexity] - Erich Grädel.

* Here is a [http://wiki.henryfarrell.net/wiki/index.php/Computer_Science list of blogs in computer science] (including several blogs who have been actively posting on this topic).