View source for Deolalikar P vs NP paper

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  '''Has since been replaced with the most recent version.'''
* [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 + &epsilon;], Aug 9 2010. '''File removed,''' Aug 11 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
** Still present in third draft, but now on page 33.
* (draft 2 + e, p.34, Def. 3.8): <math>n</math> → <math>k</math>
** Still present in third draft, but now on page 49 and Def 4.8.
* (Second draft, page 52) <math>\sum C_{li}S_i-k>0</math>  → <math>\sum C_{li}S_i+k>0 </math>
** Still present in third draft, but now on page 70.
* (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.
** Still present in third draft, but now on page 16 (and referring to Chapter 6 instead).
* (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>

== Specific issues ==

* '''The problem in the LFP section of the proof:''' As phrased by [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof#comment-5138 Albert Atserias] and [[Lindell's Critique|Steven Lindell]]:
<blockquote>
Let “polylog-parametrizable” be a property of solution spaces yet to be defined.

* Claim 1: The solution spaces of problems in P are polylog-parametrizable.
* Claim 2: The solution space of k-SAT is not polylog-parametrizable.

Now, Claim 1 could be split as follows:

* Claim 1.1: The solution spaces to problems in Monadic LFP are polylog-parametrizable.
* Claim 1.2: Every problem in LFP reduces to a problem Monadic LFP by a reduction that preserves polylog-parametrizability of the solution spaces.

From these Claim 1 would follow from the Immerman-Vardi Theorem (we need successor or linear order of course).

Perhaps Claim 1.1 could be true (we know a lot about Monadic LFP, in particular unconditional lower bounds using Hanf-Gaifman locality).

But Claim 1.2 looks very unlikely. The reduction that Deolalikar proposes is standard but definitely does not preserve anything on which we can apply Hanf-Gaifman locality. 

Specifically, (and this is adapted from [[Lindell's Critique]]) on Remark 8.5 on page 85 (third draft), it is asserted that "the [successor] relation... is monadic, and so does not introduce new edges into the Gaifman graph".  However, this is only true in the original LFP.  When encoding the LFP into a monadic LFP as is done immediately afterwards in the same remark, the relation becomes a section of a relation of higher arity (as mentioned in page 87 and Appendix A), using an induction relation.  However, this induction relation itself must be monadically encoded, and it may not have bounded degree. In fact, because of successor, it could define an ordering in two of its columns, which would render the Gaifman graph useless (indeed, the Gaifman graph could even collapse to have diameter one).
</blockquote>
* ''Placeholder for specific critique based on the structure of k-XORSAT - it seems like we're ready to phrase this one.''

== General 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 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 [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.

* '''Ordering, or lack thereof''': 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. 
* '''Boundedness and greatest fixed points''': [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 exist in other restricted CSP which are in P, but may exhibit freezing stage, as pointed by several other people.

More specifically: in the portion of the paper that is devoted to analyzing the k-SAT problem, what is the first step which works for k-SAT but breaks down completely for k-XORSAT?
* '''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. Here is a specific distribution of 2-SAT where the structure of the solution space looks similar to that of the hard cases in the k-SAT phase transition. For integers k and n, where k divides n, take variables x1,..,xn  and split them into k groups of n/k variables each. Put a uniform random assignment x1=a1...xn=an on all the variables. You can construct a 2-CNF formula with 2^{k} satisfying assignments, one of which is x1=a1...xn=an, and the other satisfying assignments are obtained by flipping the values of all variables in one of the groups. This 2-CNF formula has 2^k clusters, each cluster has hamming distance >= n/k from the others, and in each cluster all variables are frozen.  One can also "complicate" this example a bit more, make the clusters a bit more interesting, so that not all variables are frozen but still Omega(n). 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.

=== Uniformity issues ===

The following is a lightly edited excerpt from [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4918 a comment of Russell Impagliazzo]:

<blockquote>
The general approach of this paper is to try to characterize hard instances of search problems by the structure of their solution
spaces.   The problem is that this intuition is far too ambitious. It is talking about what makes INSTANCES hard, not about what makes PROBLEMS hard. Since in say, non-uniform models, individual instances or small sets of instances are not hard,
this seems to be a dead-end. There is a loophole in this paper, in that he’s talking
about the problem of extending a given partial assignment. But still, you can construct artificial easy instances so that the solution space has any particular structure. That solutions fall in well-separated clusters cannot really imply that the search problem is hard. Take any instance with exponentially many solutions and
perform a random linear transformation on the solution space, so that solution
y is “coded” by Ay. Then the complexity of search hasn’t really changed,
but the solution space is well-separated. So the characterization this paper is attempting does not seem to me to be about the right category of object.
</blockquote>

=== Locality issues ===

From [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/#comment-4677 a comment of Thomas Schwentick]:

<blockquote>
There is an another issue with the locality in remark 3 of Section 4.3. Moving from singletons to tuples destroys locality: this is because the distance of two tuples is defined on the basis of its participating elements. For example, if two tuples have a common element then their distance is (<=) 1. Thus, even if in the "meta-structure" two tuples are far apart, they can be neighbors because of their singular elements.
</blockquote>

See also the tupling issues mentioned in an earlier section.

From [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4918 a comment of Russell Impagliazzo]:

<blockquote>
The paper talks about “factoring” the computation into steps that are individually “local”.
There are many ways to formalize that steps of computation are indeed local, with FO logic one of them.
However, that does not mean that polynomial-time computation is local, because the composition of local operations is not local.
I’ve been scanning the paper for any lemma that relates the locality or other weakness of a composition to the locality of the individual steps. I haven’t seen it yet.
</blockquote>

=== Does the argument prove too much? ===

From [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/#comment-4874 a comment of Cristopher Moore]:

<blockquote>
The proof, if correct, shows that there is a poly-time samplable distribution on which k-SAT is hard on average — that hard instances are easy to generate. In Impagliazzo’s “five possible worlds” of average-case complexity, this puts us at least in Pessiland. If hard _solved_ instances are easy to generate, say through the “quiet planting” models that have been proposed, then we are in Minicrypt or Cryptomania.
</blockquote>

=== 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.)

* [http://globofthoughts.blogspot.com/2007/05/gdel-prize-naturally.html D. Sivakumar] summarizes the natural proofs concept. 
* [http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs/ Dick Lipton has a post] that among other things, explains the key intuition behind the natural proofs obstacle.

==== 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>

Note that "average case behaviour" here refers to the structure of the solution space, as opposed to the difficulty of solving a random instance of the problem.

Followup by [http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np#comment-4988 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>

See also the previous section on issues with random k-SAT for closely related points.

== 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.
* [http://www.reddit.com/r/programming/comments/cytlp/serious_attempt_that_p_np_originally_posted_in/ Serious attempt that P != NP], Reddit, 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.
* [http://digg.com/general_sciences/PnNP_has_been_proven P≠NP has been proven?], Digg, 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, Digital tools, Forbes blogs, 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, Digital tools, Forbes blogs, August 11 2010.
* [http://www.psychologytoday.com/blog/nature-brain-and-culture/201008/p-np-and-is-academia-inhospitable-big-discoveries P, NP, And Is Academia Inhospitable to Big Discoveries?], Mark Changizi, Psychology Today, August 11 2010.
* [http://www.livemint.com/2010/08/10230113/Indian-scientist-offers-proof.html?h=E Indian scientist offers proof for P=NP riddle], Samanth Subramanian, Livemint.com, August 11 2010.
* [http://www.theregister.co.uk/2010/08/11/the_p_versus_np_problem/ HP boffin claims million-dollar maths prize], Rik Myslewski, The Register, August 11 2010.
* [http://en.wikinews.org/wiki/P%3DNP_math_problem_reported_solved?dpl_id=200299 P=NP math problem reported solved], Wikinews, August 11 2010.

====12th August====
* [http://www.hindu.com/2010/08/12/stories/2010081257181300.htm Indian scientist proposes solution to math problem], Shyam Ranganathan, The Hindu, Aug 12, 2010.
* [http://www.i-programmer.info/news/112-theory/1161-update-on-the-proof-of-pnp.html Update on the Proof of P != NP?] Mike James, I Programmer, August 12, 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://www.jtolds.com/newsletter/2010/8/11/watching-great-mathematics-unfold Watching great mathematics unfold], JT Olds, 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://claymath.msri.org/sipser2006.mov Beyond Computation: The P vs. NP Problem] Video of lecture for general public, Michael Sipser 2006
* [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).