Polymath Wiki - User contributions [en]

Random k-SAT

2010-08-11T22:14:56Z

Krzakala:

Below are some notes of Dimitris Achlioptas, with additions from Lenka Zdeborova.

This is an attempt to clarify some issues regarding "d1RSB", "clustering", "freezing", "condensation" in random k-SAT. An effort is made to keep the discussion rather generic and, less successfully, short. This picture originates from statistical physics theories, but we stress results that are known rigorously. References to original literature are mostly not given and this should be fixed at some later point.

=== The setting: ===

* A set of n variables all with the same finite domain of size d, e.g., d=2 in k-SAT.
* A collection of constraints on the variables, each constraint binding k of the n variables, e.g., k=2 in graph coloring.

Typically, the collection consists of "all possible constraints of a certain kind on the n variables", e.g., all <math>2^k \binom{n}{k}</math> clauses of length k in k-SAT, or all <math>\binom{n}{2}</math> edges, i.e., "not equal" constraints, in graph coloring.

* It will be easier to think of the formation of random instances as a "process", in which constraints are added one by one, by selecting one uniformly random constraint from the collection, among those that have not yet been selected (for technical reasons, it often helps to allow selection with replacement, but this turns out to be inconsequential.)
* Finally, it also helps to think of what is called in physics the "energy landscape", i.e., the function counting the number of violated constraints for each value assignment. So, in particular, solutions correspond to the value assignments (points) where the energy is zero.
* For any given problem, let <math>S_n(t)</math> denote the set of solutions of a random instance after t constraints have been added. (Clearly, <math>S_n(t)</math> is a random variable, so everything below refers to the "typical" behavior of <math>S_n</math>.)
* Say that two value assignments are adjacent if they have Hamming distance 1. Under this notion of adjacency, we will look at the "connected components" of <math>S_n</math>, also called "clusters". (Sometimes one replaces "Hamming distance 1" with "subextensive Hamming distance" with no essential difference. This does not seem to be a consequential issue.)

With the above in mind, below is a "voiceover" for the video <math>S_n(0), S_n(1), S_n(2),\ldots</math>.

* Clearly, at t=0, every value assignment is a solution, i.e., <math>S_n(0)</math> is everything, and there is only one cluster.
* Now, fix <math>\delta >0</math> and let <math>X=X(\delta)</math> be the random variable equal to: the smallest number of clusters such that their union contains all but a delta-fraction of <math>S_n</math>.

=== Clustering ===

* It is predicted [MPZ02], for any finite <math>\delta</math>, X undergoes a "phase transition" and goes from 1 to "exponentially many" during the addition of <math>o(n)</math> constraints around a critical, problem-specific constraints-to-variables ratio. The later phase is called clustered. Clustering is a very generic phenomenon for random CSPs.

* Existence of the clustered phase has been rigorously established for random k-SAT [DMM+08,AR09], random graph k-coloring, random NAE k-SAT, and a number of other problems, in each case for all values of <math>k > k_0</math> (where <math>k_0</math> is finite and problem dependent) there is a constraint density t/n beyond which <math>S_n(0)</math> is clustered.

* If one thinks in terms of the energy landscape, clustering means that we go from a world with a single big energy-zero valley, to a world with exponentially many smaller energy-zero valleys (and no big energy zero valley).

Of course, to have valleys you need mountains. In particular, another thing that has been rigorously established is that the valleys are "landlocked". Namely:

* For some region of parameters every pair of valleys has Hamming distance <math>\Omega(n)</math>, and every path connecting solutions in distinct valleys, must go through a point in which the energy function has value <math>\Omega(n)</math>. [By the Lipschitzness of the energy function, in fact, the path must go through <math>\Omega(n)</math> such points].

=== 1RSB ===

* 1RSB stands for "1-step Replica Symmetry Breaking" [KMR+07]. Consider a single variable flip Markov process satisfying the detailed balance condition with respect to uniform distribution over <math>S_n</math> (e.g. Glauber dynamics). Whereas in the "Replica Symmetric" (RS) phase this process is able to sample uniformly <math>S_n</math> in time <math>O(n)</math>, the 1RSB phase is defined as phase where uniform sampling with this process requires time exponential in n.

* The uniform measure over <math>S_n</math> ceases to be an extremal Gibbs measure at the 1RSB transition. In the 1RSB phase <math>S_n</math> is a union of exponentially many extremal Gibbs measures, sometimes called states in physics. The reconstruction problem of graphs is solvable only and only in the d1RSB phase. Equivalence of the three definitions of d1RSB given above in random K-SAT is predicted in statistical physics theories, and is so far proven only partially. Statistical physics theories predict sharp transition from the RS to the d1RSB phase and their locations.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. For the definition of condensation see below.

Note that clustering implies 1RSB but 1RSB does not imply clustering defined as above.

A word of caution: In statistical physics literature clustering is almost always defined via 1RSB, not as above.

=== Freezing===
* The next relevant phenomenon is the emergence of "frozen variables" [ZK07,S07]. Concretely, a variable is frozen in a cluster if it takes the same value in all assignments of that cluster. Note that the same variable can be frozen to different values in different clusters and can be frozen in some clusters but not in others. Freezing implies clustering, but clustering can (and does) occur without freezing.

Regarding frozen variables we rigorously know for instance the following:

# For <math>k>k_1</math> there is a constraint density in random K-SAT beyond which a uniformly random solution, with high probability, has <math>\Omega(n)</math> frozen variables.
# As k is increased (which in k-SAT means the length of the clauses, while in coloring the number of colors), the constraint density beyond which emergence of frozen variables is proven agrees in the leading order in k with the constraint density beyond which clustering appears.
# (Perhaps most importantly) It was proven [AR09] for significantly larger constraint densities that while <math>S_n</math> still consists of "exponentially many clusters of roughly equal size", with high probability, EVERY SINGLE cluster contains <math>\Omega(n)</math> frozen variables. (And indeed, the fraction of variables that are frozen tends to 1 with k.)

To put this a bit more starkly: For a number of random CSP problems, for a sizable fraction of the satisfiable regime of each problem, the space of solutions looks like an "error-correcting code with fuzz". The "fuzz" is the little cloud that forms by jiggling the non-frozen variables. Again, it's important to remember that the set of frozen variables differs from cluster to cluster and that, moreover, a variable can be frozen to different values in different clusters.

* After <math>S_n</math> has reached the above "error-correcting code with fuzz" state, it is clear that every single constraint added from now on will "kill", in expectation, a constant fraction of all clusters (since each cluster has a constant fraction of frozen variables and, therefore, a constant probability of being killed).

=== Condensation ===
* Consider two variables that are far away from each other (in terms of the shortest path between them), the correlation between these two variables is defined as <math>E(x_1 x_2) - E(x_1) E(x_2)</math>, where the average is over the uniform measure over <math>S_n</math>. In the phase called "condensed" [KMR+07] the correlation between a typical couple of variables does not go to zero as their distance goes to zero.

* In the condensed phase only a handful (finitely-many-in-expectation) of Gibbs states, capture all but a vanishing fraction of <math>S_n</math>, while exponentially many smaller Gibbs states still exist. In the regime where the rigorous results about clustering and freezing hold the term "Gibbs state" can be interchanged for "cluster" in this statement.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. The d1RSB stands for "dynamic one-step replica symmetry breaking".

=== Random 3-SAT versus large k-SAT ===
* When k is large, it is rigorously known that the 1RSB, clustering and freezing (of most clusters) happens at the same (in the first order in k) constraint density [AM06,KMR+07]. Whereas the condensation and the satisfiability threshold happen nearby each other and much beyond clustering. And no algorithm has been known to work in the clustered phase -- an open problem for more than 30 years.

* The situation is crucially different when k is small. In 3-SAT (and also 3-COL) for instance statistical physics predicts that the 1RSB and condensation transition coincide. Hence there is no d1RSB phase. And the freezing happens relatively nearby to the satisfiability threshold. In 3-coloring the 1RSB threshold is when every variable has on average 4 neighbors. Whereas polynomial algorithms are known to work rigorously up to 4.03.

=== Locked constraint satisfaction problems ===
* Fortunately there are NP-complete CSPs where the description of the space of solutions is much simpler than in random K-SAT [ZM08]. In the random locked CSP's 1RSB, clustering and freezing transitions coincide. And no condensed phase exists.

* Consider for instance k-in-2k SAT, that is each clause contains 2k variables and is satisfied if and only if k of the variables are TRUE and k are FALSE (no negations present). And consider every variable being included in at least 3 clauses. Then the space of solutions consists of single configurations separated by extensive Hamming distance in the whole satisfiable region.

=== Where the hard instances are? ===
* The empirical finding [CKT91] that hardest k-SAT instances are around the satisfiability threshold is well known but not precise. Despites initial beliefs, the example of 3-coloring testifies that neither the 1RSB nor the condensation in the space of solutions pose general algorithmic barriers [AM03,ZK07]. On the other hand no polynomial algorithm is known to work (not even empirically) in any of the NP-complete problems in the phase where ALL clusters are frozen. That has lead to the conjecture that such problems are especially hard [ZK07].

=== Random k-XOR-SAT ===
Finally, what about random k-XOR-SAT ?

* First, a technical point. If one does indeed generate instances by selecting the variables in each constraint uniformly at random (without insisting that each variable has degree at least 2 as one does in LDPC codes), then there will be variables which appears in 0 or 1 constraints. Clearly, such variables can be "repeatedly removed" leaving a "core" structure. It is clear that if one finds a solution to the core, then this solution can be trivially extended to the rest. OK, what about solutions to this core?
* Well, this core does indeed behave like -- you guessed it -- an error-correcting code, indeed one with absolutely no fuzz: each connected component has size 1. Intuitively, the reason is that if one is at a "codeword" and changes the value of a single variable V, since we are dealing with parity constraints, this will require flipping some other variable in each of the constraints that contain V, and since the underlying (hyper-/factor)graph is an expander, such "forced changes" will proliferate. Note that such a proliferation does not necessarily occur in random k-SAT or graph coloring, as it's possible to change a single variable and still have every constraint be satisfied. This "redundancy" in the solutions is precisely what gives rise to the aforementioned "fuzz" for those problems.
* Finally, the heart of the matter, and what I believe is meant by Deolalikar when he speaks of "independent parameters". The cores/codewords in random k-XOR-SAT, are linearly related. In contrast, in random k-SAT we have no reason to think that they should be and one can, indeed, think of them as (more or less) randomly placed points inside the set of all value assignments, thus requiring "many" parameters to be specified. Alternatively, one can think of the random CSP instances as taking the randomness used to define the factor graph of the instance and "lifting it" to the high-dimensional space of solutions, by creating "randomly placed" pockets of solutions (clusters).

== References ==
* [AM03] [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-49M05RK-3&_user=2493154&_coverDate=09%2F30%2F2003&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_rerunOrigin=scholar.google&_acct=C000057551&_version=1&_urlVersion=0&_userid=2493154&md5=f13f9cfd23914c9b7bcd5274e5d4b157 Almost all graphs with average degree 4 are 3-colorable], D. Achlioptas and C. Moore, Journal of Computer and System Sciences 67 (2003) 441–471.
* [AM06] [http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000036000003000740000001&idtype=cvips&gifs=yes Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold], D. Achlioptas and C. Moore, SIAM J. Comput. Volume 36, Issue 3, pp. 740-762 (2006) .
* [AR09] [http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000039000001000260000001&idtype=cvips&gifs=yes Random Formulas Have Frozen Variables], D. Achlioptas and F. Ricci-Tersenghi, SIAM J. Comput. Volume 39, Issue 1, pp. 260-280 (2009)
* [CKT91] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3555&rep=rep1&type=pdf Where the Really Hard Problems Are ?], P Cheeseman, B Kanefsky, WM Taylor, Proccedings IJCAI-91, 1991, 163-169.
* [DMM+08] [http://portal.acm.org/citation.cfm?id=1347453.1347620 Pairs of SAT Assignments and Clustering in Random Boolean Formulae] H. Daude, M. Mézard, T. Mora, R. Zecchina, Theor. Comp. Sci. 393 (2008) 260-279.
* [KMR+07] [http://www.pnas.org/content/104/25/10318.abstract Gibbs states and the set of solutions of random constraint satisfaction problems], F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborova, PNAS 2007, 104, 10318-10323.
* [MPZ02] [http://www.sciencemag.org/cgi/content/abstract/297/5582/812?ijkey=bb692e28fb17ceba785ae57d9c5db2cf21a5fa62&keytype2=tf_ipsecsha Analytic and Algorithmic Solution of Random Satisfiability Problems ], M. Mezard M, G. Parisi and R. Zecchina, 2002 Science 297:812–815.
* [S07] [http://www.springerlink.com/content/n710514276010144/ On the Freezing of Variables in Random Constraint Satisfaction Problems], G. Semerjian, J. Stat. Phys. 130, 251 (2008).
* [ZK07] [http://pre.aps.org/abstract/PRE/v76/i3/e031131 Phase transitions in the coloring of random graphs], L. Zdeborova and F. Krzakala, Phys. Rev. E 76, 031131 (2007)
* [ZM08] [http://iopscience.iop.org/1742-5468/2008/12/P12004 Constraint satisfaction problems with isolated solutions are hard], L. Zdeborova and M. Mezard, J. Stat. Mech. (2008) P12004.

Random k-SAT

2010-08-11T22:04:53Z

Krzakala:

Below are some notes of Dimitris Achlioptas, with additions from Lenka Zdeborova.

This is an attempt to clarify some issues regarding "d1RSB", "clustering", "freezing", "condensation" in random k-SAT. An effort is made to keep the discussion rather generic and, less successfully, short. This picture originates from statistical physics theories, but we stress results that are known rigorously. References to original literature are mostly not given and this should be fixed at some later point.

=== The setting: ===

* A set of n variables all with the same finite domain of size d, e.g., d=2 in k-SAT.
* A collection of constraints on the variables, each constraint binding k of the n variables, e.g., k=2 in graph coloring.

Typically, the collection consists of "all possible constraints of a certain kind on the n variables", e.g., all <math>2^k \binom{n}{k}</math> clauses of length k in k-SAT, or all <math>\binom{n}{2}</math> edges, i.e., "not equal" constraints, in graph coloring.

* It will be easier to think of the formation of random instances as a "process", in which constraints are added one by one, by selecting one uniformly random constraint from the collection, among those that have not yet been selected (for technical reasons, it often helps to allow selection with replacement, but this turns out to be inconsequential.)
* Finally, it also helps to think of what is called in physics the "energy landscape", i.e., the function counting the number of violated constraints for each value assignment. So, in particular, solutions correspond to the value assignments (points) where the energy is zero.
* For any given problem, let <math>S_n(t)</math> denote the set of solutions of a random instance after t constraints have been added. (Clearly, <math>S_n(t)</math> is a random variable, so everything below refers to the "typical" behavior of <math>S_n</math>.)
* Say that two value assignments are adjacent if they have Hamming distance 1. Under this notion of adjacency, we will look at the "connected components" of <math>S_n</math>, also called "clusters". (Sometimes one replaces "Hamming distance 1" with "subextensive Hamming distance" with no essential difference. This does not seem to be a consequential issue.)

With the above in mind, below is a "voiceover" for the video <math>S_n(0), S_n(1), S_n(2),\ldots</math>.

* Clearly, at t=0, every value assignment is a solution, i.e., <math>S_n(0)</math> is everything, and there is only one cluster.
* Now, fix <math>\delta >0</math> and let <math>X=X(\delta)</math> be the random variable equal to: the smallest number of clusters such that their union contains all but a delta-fraction of <math>S_n</math>.

=== Clustering ===

* It is predicted [MPZ02], for any finite <math>\delta</math>, X undergoes a "phase transition" and goes from 1 to "exponentially many" during the addition of <math>o(n)</math> constraints around a critical, problem-specific constraints-to-variables ratio. The later phase is called clustered. Clustering is a very generic phenomenon for random CSPs.

* Existence of the clustered phase has been rigorously established for random k-SAT [DMM+08,AR09], random graph k-coloring, random NAE k-SAT, and a number of other problems, in each case for all values of <math>k > k_0</math> (where <math>k_0</math> is finite and problem dependent) there is a constraint density t/n beyond which <math>S_n(0)</math> is clustered.

* If one thinks in terms of the energy landscape, clustering means that we go from a world with a single big energy-zero valley, to a world with exponentially many smaller energy-zero valleys (and no big energy zero valley).

Of course, to have valleys you need mountains. In particular, another thing that has been rigorously established is that the valleys are "landlocked". Namely:

* For some region of parameters every pair of valleys has Hamming distance <math>\Omega(n)</math>, and every path connecting solutions in distinct valleys, must go through a point in which the energy function has value <math>\Omega(n)</math>. [By the Lipschitzness of the energy function, in fact, the path must go through <math>\Omega(n)</math> such points].

=== 1RSB ===

* 1RSB stands for "1-step Replica Symmetry Breaking" [KLR+07]. Consider a single variable flip Markov process satisfying the detailed balance condition with respect to uniform distribution over <math>S_n</math> (e.g. Glauber dynamics). Whereas in the "Replica Symmetric" (RS) phase this process is able to sample uniformly <math>S_n</math> in time <math>O(n)</math>, the 1RSB phase is defined as phase where uniform sampling with this process requires time exponential in n.

* The uniform measure over <math>S_n</math> ceases to be an extremal Gibbs measure at the 1RSB transition. In the 1RSB phase <math>S_n</math> is a union of exponentially many extremal Gibbs measures, sometimes called states in physics. The reconstruction problem of graphs is solvable only and only in the d1RSB phase. Equivalence of the three definitions of d1RSB given above in random K-SAT is predicted in statistical physics theories, and is so far proven only partially. Statistical physics theories predict sharp transition from the RS to the d1RSB phase and their locations.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. For the definition of condensation see below.

Note that clustering implies 1RSB but 1RSB does not imply clustering defined as above.

A word of caution: In statistical physics literature clustering is almost always defined via 1RSB, not as above.

=== Freezing===
* The next relevant phenomenon is the emergence of "frozen variables" [ZK07,S07]. Concretely, a variable is frozen in a cluster if it takes the same value in all assignments of that cluster. Note that the same variable can be frozen to different values in different clusters and can be frozen in some clusters but not in others. Freezing implies clustering, but clustering can (and does) occur without freezing.

Regarding frozen variables we rigorously know for instance the following:

# For <math>k>k_1</math> there is a constraint density in random K-SAT beyond which a uniformly random solution, with high probability, has <math>\Omega(n)</math> frozen variables.
# As k is increased (which in k-SAT means the length of the clauses, while in coloring the number of colors), the constraint density beyond which emergence of frozen variables is proven agrees in the leading order in k with the constraint density beyond which clustering appears.
# (Perhaps most importantly) It was proven [AR09] for significantly larger constraint densities that while <math>S_n</math> still consists of "exponentially many clusters of roughly equal size", with high probability, EVERY SINGLE cluster contains <math>\Omega(n)</math> frozen variables. (And indeed, the fraction of variables that are frozen tends to 1 with k.)

To put this a bit more starkly: For a number of random CSP problems, for a sizable fraction of the satisfiable regime of each problem, the space of solutions looks like an "error-correcting code with fuzz". The "fuzz" is the little cloud that forms by jiggling the non-frozen variables. Again, it's important to remember that the set of frozen variables differs from cluster to cluster and that, moreover, a variable can be frozen to different values in different clusters.

* After <math>S_n</math> has reached the above "error-correcting code with fuzz" state, it is clear that every single constraint added from now on will "kill", in expectation, a constant fraction of all clusters (since each cluster has a constant fraction of frozen variables and, therefore, a constant probability of being killed).

=== Condensation ===
* Consider two variables that are far away from each other (in terms of the shortest path between them), the correlation between these two variables is defined as <math>E(x_1 x_2) - E(x_1) E(x_2)</math>, where the average is over the uniform measure over <math>S_n</math>. In the phase called "condensed" [KLR+07] the correlation between a typical couple of variables does not go to zero as their distance goes to zero.

* In the condensed phase only a handful (finitely-many-in-expectation) of Gibbs states, capture all but a vanishing fraction of <math>S_n</math>, while exponentially many smaller Gibbs states still exist. In the regime where the rigorous results about clustering and freezing hold the term "Gibbs state" can be interchanged for "cluster" in this statement.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. The d1RSB stands for "dynamic one-step replica symmetry breaking".

=== Random 3-SAT versus large k-SAT ===
* When k is large, it is rigorously known that the 1RSB, clustering and freezing (of most clusters) happens at the same (in the first order in k) constraint density. Whereas the condensation and the satisfiability threshold happen nearby each other and much beyond clustering. And no algorithm has been known to work in the clustered phase -- an open problem for more than 30 years.

* The situation is crucially different when k is small. In 3-SAT (and also 3-COL) for instance statistical physics predicts that the 1RSB and condensation transition coincide. Hence there is no d1RSB phase. And the freezing happens relatively nearby to the satisfiability threshold. In 3-coloring the 1RSB threshold is when every variable has on average 4 neighbors. Whereas polynomial algorithms are known to work rigorously up to 4.03.

=== Locked constraint satisfaction problems ===
* Fortunately there are NP-complete CSPs where the description of the space of solutions is much simpler than in random K-SAT. In the random locked CSP's 1RSB, clustering and freezing transitions coincide. And no condensed phase exists.

* Consider for instance k-in-2k SAT, that is each clause contains 2k variables and is satisfied if and only if k of the variables are TRUE and k are FALSE (no negations present). And consider every variable being included in at least 3 clauses. Then the space of solutions consists of single configurations separated by extensive Hamming distance in the whole satisfiable region.

=== Where the hard instances are? ===
* The empirical finding [CKT91] that hardest k-SAT instances are around the satisfiability threshold is well known but not precise. Despites initial beliefs, the example of 3-coloring testifies that neither the 1RSB nor the condensation in the space of solutions pose general algorithmic barriers [AM03,ZK07]. On the other hand no polynomial algorithm is known to work (not even empirically) in any of the NP-complete problems in the phase where ALL clusters are frozen. That has lead to the conjecture that such problems are especially hard [ZK07].

=== Random k-XOR-SAT ===
Finally, what about random k-XOR-SAT ?

* First, a technical point. If one does indeed generate instances by selecting the variables in each constraint uniformly at random (without insisting that each variable has degree at least 2 as one does in LDPC codes), then there will be variables which appears in 0 or 1 constraints. Clearly, such variables can be "repeatedly removed" leaving a "core" structure. It is clear that if one finds a solution to the core, then this solution can be trivially extended to the rest. OK, what about solutions to this core?
* Well, this core does indeed behave like -- you guessed it -- an error-correcting code, indeed one with absolutely no fuzz: each connected component has size 1. Intuitively, the reason is that if one is at a "codeword" and changes the value of a single variable V, since we are dealing with parity constraints, this will require flipping some other variable in each of the constraints that contain V, and since the underlying (hyper-/factor)graph is an expander, such "forced changes" will proliferate. Note that such a proliferation does not necessarily occur in random k-SAT or graph coloring, as it's possible to change a single variable and still have every constraint be satisfied. This "redundancy" in the solutions is precisely what gives rise to the aforementioned "fuzz" for those problems.
* Finally, the heart of the matter, and what I believe is meant by Deolalikar when he speaks of "independent parameters". The cores/codewords in random k-XOR-SAT, are linearly related. In contrast, in random k-SAT we have no reason to think that they should be and one can, indeed, think of them as (more or less) randomly placed points inside the set of all value assignments, thus requiring "many" parameters to be specified. Alternatively, one can think of the random CSP instances as taking the randomness used to define the factor graph of the instance and "lifting it" to the high-dimensional space of solutions, by creating "randomly placed" pockets of solutions (clusters).

== References ==
* [AM03] [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-49M05RK-3&_user=2493154&_coverDate=09%2F30%2F2003&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_rerunOrigin=scholar.google&_acct=C000057551&_version=1&_urlVersion=0&_userid=2493154&md5=f13f9cfd23914c9b7bcd5274e5d4b157 Almost all graphs with average degree 4 are 3-colorable], D. Achlioptas and C. Moore, Journal of Computer and System Sciences 67 (2003) 441–471.
* [AR09] [http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SMJCAT000039000001000260000001&idtype=cvips&gifs=yes Random Formulas Have Frozen Variables], D. Achlioptas and F. Ricci-Tersenghi, SIAM J. Comput. Volume 39, Issue 1, pp. 260-280 (2009)
* [CKT91] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3555&rep=rep1&type=pdf Where the Really Hard Problems Are ?], P Cheeseman, B Kanefsky, WM Taylor, Proccedings IJCAI-91, 1991, 163-169.
* [DMM+08] [http://portal.acm.org/citation.cfm?id=1347453.1347620 Pairs of SAT Assignments and Clustering in Random Boolean Formulae] H. Daude, M. Mézard, T. Mora, R. Zecchina, Theor. Comp. Sci. 393 (2008) 260-279.
* [KLR+07] [http://www.pnas.org/content/104/25/10318.abstract Gibbs states and the set of solutions of random constraint satisfaction problems], F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborova, PNAS 2007, 104, 10318-10323.
* [MPZ02] [http://www.sciencemag.org/cgi/content/abstract/297/5582/812?ijkey=bb692e28fb17ceba785ae57d9c5db2cf21a5fa62&keytype2=tf_ipsecsha Analytic and Algorithmic Solution of Random Satisfiability Problems ], M. Mezard M, G. Parisi and R. Zecchina, 2002 Science 297:812–815.
* [S07] [http://www.springerlink.com/content/n710514276010144/ On the Freezing of Variables in Random Constraint Satisfaction Problems], G. Semerjian, J. Stat. Phys. 130, 251 (2008).
* [ZK07] [http://pre.aps.org/abstract/PRE/v76/i3/e031131 Phase transitions in the coloring of random graphs], L. Zdeborova and F. Krzakala, Phys. Rev. E 76, 031131 (2007)

Random k-SAT

2010-08-11T21:32:56Z

Krzakala:

Below are some notes of Dimitris Achlioptas, with additions from Lenka Zdeborova.

This is an attempt to clarify some issues regarding "d1RSB", "clustering", "freezing", "condensation" in random k-SAT. An effort is made to keep the discussion rather generic and, less successfully, short. This picture originates from statistical physics theories, but we stress results that are known rigorously. References to original literature are mostly not given and this should be fixed at some later point.

=== The setting: ===

* A set of n variables all with the same finite domain of size d, e.g., d=2 in k-SAT.
* A collection of constraints on the variables, each constraint binding k of the n variables, e.g., k=2 in graph coloring.

Typically, the collection consists of "all possible constraints of a certain kind on the n variables", e.g., all <math>2^k \binom{n}{k}</math> clauses of length k in k-SAT, or all <math>\binom{n}{2}</math> edges, i.e., "not equal" constraints, in graph coloring.

* It will be easier to think of the formation of random instances as a "process", in which constraints are added one by one, by selecting one uniformly random constraint from the collection, among those that have not yet been selected (for technical reasons, it often helps to allow selection with replacement, but this turns out to be inconsequential.)
* Finally, it also helps to think of what is called in physics the "energy landscape", i.e., the function counting the number of violated constraints for each value assignment. So, in particular, solutions correspond to the value assignments (points) where the energy is zero.
* For any given problem, let <math>S_n(t)</math> denote the set of solutions of a random instance after t constraints have been added. (Clearly, <math>S_n(t)</math> is a random variable, so everything below refers to the "typical" behavior of <math>S_n</math>.)
* Say that two value assignments are adjacent if they have Hamming distance 1. Under this notion of adjacency, we will look at the "connected components" of <math>S_n</math>, also called "clusters". (Sometimes one replaces "Hamming distance 1" with "subextensive Hamming distance" with no essential difference. This does not seem to be a consequential issue.)

With the above in mind, below is a "voiceover" for the video <math>S_n(0), S_n(1), S_n(2),\ldots</math>.

* Clearly, at t=0, every value assignment is a solution, i.e., <math>S_n(0)</math> is everything, and there is only one cluster.
* Now, fix <math>\delta >0</math> and let <math>X=X(\delta)</math> be the random variable equal to: the smallest number of clusters such that their union contains all but a delta-fraction of <math>S_n</math>.

=== Clustering ===

* It is predicted, for any finite <math>\delta</math>, X undergoes a "phase transition" and goes from 1 to "exponentially many" during the addition of <math>o(n)</math> constraints around a critical, problem-specific constraints-to-variables ratio. The later phase is called clustered. Clustering is a very generic phenomenon for random CSPs.

* Existence of the clustered phase has been rigorously established for random k-SAT, random graph k-coloring, random NAE k-SAT, and a number of other problems, in each case for all values of <math>k > k_0</math> (where <math>k_0</math> is finite and problem dependent) there is a constraint density t/n beyond which <math>S_n(0)</math> is clustered.

* If one thinks in terms of the energy landscape, clustering means that we go from a world with a single big energy-zero valley, to a world with exponentially many smaller energy-zero valleys (and no big energy zero valley).

Of course, to have valleys you need mountains. In particular, another thing that has been rigorously established is that the valleys are "landlocked". Namely:

* For some region of parameters every pair of valleys has Hamming distance <math>\Omega(n)</math>, and every path connecting solutions in distinct valleys, must go through a point in which the energy function has value <math>\Omega(n)</math>. [By the Lipschitzness of the energy function, in fact, the path must go through <math>\Omega(n)</math> such points].

=== 1RSB ===

* 1RSB stands for "1-step Replica Symmetry Breaking". Consider a single variable flip Markov process satisfying the detailed balance condition with respect to uniform distribution over <math>S_n</math> (e.g. Glauber dynamics). Whereas in the "Replica Symmetric" (RS) phase this process is able to sample uniformly <math>S_n</math> in time <math>O(n)</math>, the 1RSB phase is defined as phase where uniform sampling with this process requires time exponential in n.

* The uniform measure over <math>S_n</math> ceases to be an extremal Gibbs measure at the 1RSB transition. In the 1RSB phase <math>S_n</math> is a union of exponentially many extremal Gibbs measures, sometimes called states in physics. The reconstruction problem of graphs is solvable only and only in the d1RSB phase. Equivalence of the three definitions of d1RSB given above in random K-SAT is predicted in statistical physics theories, and is so far proven only partially. Statistical physics theories predict sharp transition from the RS to the d1RSB phase and their locations.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. For the definition of condensation see below.

Note that clustering implies 1RSB but 1RSB does not imply clustering defined as above.

A word of caution: In statistical physics literature clustering is almost always defined via 1RSB, not as above.

=== Freezing===
* The next relevant phenomenon is the emergence of "frozen variables". Concretely, a variable is frozen in a cluster if it takes the same value in all assignments of that cluster. Note that the same variable can be frozen to different values in different clusters and can be frozen in some clusters but not in others. Freezing implies clustering, but clustering can (and does) occur without freezing.

Regarding frozen variables we rigorously know for instance the following:

# For <math>k>k_1</math> there is a constraint density in random K-SAT beyond which a uniformly random solution, with high probability, has <math>\Omega(n)</math> frozen variables.
# As k is increased (which in k-SAT means the length of the clauses, while in coloring the number of colors), the constraint density beyond which emergence of frozen variables is proven agrees in the leading order in k with the constraint density beyond which clustering appears.
# (Perhaps most importantly) It was proven for significantly larger constraint densities that while <math>S_n</math> still consists of "exponentially many clusters of roughly equal size", with high probability, EVERY SINGLE cluster contains <math>\Omega(n)</math> frozen variables. (And indeed, the fraction of variables that are frozen tends to 1 with k.)

To put this a bit more starkly: For a number of random CSP problems, for a sizable fraction of the satisfiable regime of each problem, the space of solutions looks like an "error-correcting code with fuzz". The "fuzz" is the little cloud that forms by jiggling the non-frozen variables. Again, it's important to remember that the set of frozen variables differs from cluster to cluster and that, moreover, a variable can be frozen to different values in different clusters.

* After <math>S_n</math> has reached the above "error-correcting code with fuzz" state, it is clear that every single constraint added from now on will "kill", in expectation, a constant fraction of all clusters (since each cluster has a constant fraction of frozen variables and, therefore, a constant probability of being killed).

=== Condensation ===
* Consider two variables that are far away from each other (in terms of the shortest path between them), the correlation between these two variables is defined as <math>E(x_1 x_2) - E(x_1) E(x_2)</math>, where the average is over the uniform measure over <math>S_n</math>. In the phase called "condensed" the correlation between a typical couple of variables does not go to zero as their distance goes to zero.

* In the condensed phase only a handful (finitely-many-in-expectation) of Gibbs states, capture all but a vanishing fraction of <math>S_n</math>, while exponentially many smaller Gibbs states still exist. In the regime where the rigorous results about clustering and freezing hold the term "Gibbs state" can be interchanged for "cluster" in this statement.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. The d1RSB stands for "dynamic one-step replica symmetry breaking".

=== Random 3-SAT versus large k-SAT ===
* When k is large, it is rigorously known that the 1RSB, clustering and freezing (of most clusters) happens at the same (in the first order in k) constraint density. Whereas the condensation and the satisfiability threshold happen nearby each other and much beyond clustering. And no algorithm has been known to work in the clustered phase -- an open problem for more than 30 years.

* The situation is crucially different when k is small. In 3-SAT (and also 3-COL) for instance statistical physics predicts that the 1RSB and condensation transition coincide. Hence there is no d1RSB phase. And the freezing happens relatively nearby to the satisfiability threshold. In 3-coloring the 1RSB threshold is when every variable has on average 4 neighbors. Whereas polynomial algorithms are known to work rigorously up to 4.03.

=== Locked constraint satisfaction problems ===
* Fortunately there are NP-complete CSPs where the description of the space of solutions is much simpler than in random K-SAT. In the random locked CSP's 1RSB, clustering and freezing transitions coincide. And no condensed phase exists.

* Consider for instance k-in-2k SAT, that is each clause contains 2k variables and is satisfied if and only if k of the variables are TRUE and k are FALSE (no negations present). And consider every variable being included in at least 3 clauses. Then the space of solutions consists of single configurations separated by extensive Hamming distance in the whole satisfiable region.

=== Where the hard instances are? ===
* The empirical finding that hardest k-SAT instances are around the satisfiability threshold is well known but not precise. The example of 3-coloring testifies that neither the 1RSB not the condensation in the space of solutions pose general algorithmic barriers. On the other hand no polynomial algorithm is known to work (not even empirically) in any of the NP-complete problems in the phase where ALL clusters are frozen.

=== Random k-XOR-SAT ===
Finally, what about random k-XOR-SAT ?

* First, a technical point. If one does indeed generate instances by selecting the variables in each constraint uniformly at random (without insisting that each variable has degree at least 2 as one does in LDPC codes), then there will be variables which appears in 0 or 1 constraints. Clearly, such variables can be "repeatedly removed" leaving a "core" structure. It is clear that if one finds a solution to the core, then this solution can be trivially extended to the rest. OK, what about solutions to this core?
* Well, this core does indeed behave like -- you guessed it -- an error-correcting code, indeed one with absolutely no fuzz: each connected component has size 1. Intuitively, the reason is that if one is at a "codeword" and changes the value of a single variable V, since we are dealing with parity constraints, this will require flipping some other variable in each of the constraints that contain V, and since the underlying (hyper-/factor)graph is an expander, such "forced changes" will proliferate. Note that such a proliferation does not necessarily occur in random k-SAT or graph coloring, as it's possible to change a single variable and still have every constraint be satisfied. This "redundancy" in the solutions is precisely what gives rise to the aforementioned "fuzz" for those problems.
* Finally, the heart of the matter, and what I believe is meant by Deolalikar when he speaks of "independent parameters". The cores/codewords in random k-XOR-SAT, are linearly related. In contrast, in random k-SAT we have no reason to think that they should be and one can, indeed, think of them as (more or less) randomly placed points inside the set of all value assignments, thus requiring "many" parameters to be specified. Alternatively, one can think of the random CSP instances as taking the randomness used to define the factor graph of the instance and "lifting it" to the high-dimensional space of solutions, by creating "randomly placed" pockets of solutions (clusters).

== References ==

* [CKT91] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3555&rep=rep1&type=pdf Where the Really Hard Problems Are ?], P Cheeseman, B Kanefsky, WM Taylor, Proccedings IJCAI-91, 1991, 163-169.
* [KLR+07] [http://www.pnas.org/content/104/25/10318.abstract Gibbs states and the set of solutions of random constraint satisfaction problems], F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian and L. Zdeborova, PNAS 2007, 104, 10318-10323.
* [MPZ02] [http://www.sciencemag.org/cgi/content/abstract/297/5582/812?ijkey=bb692e28fb17ceba785ae57d9c5db2cf21a5fa62&keytype2=tf_ipsecsha Analytic and Algorithmic Solution of Random Satisfiability Problems ] M. Mezard M, G. Parisi and R. Zecchina, 2002 Science 297:812–815.

Random k-SAT

2010-08-11T21:24:32Z

Krzakala:

Below are some notes of Dimitris Achlioptas, with additions from Lenka Zdeborova.

This is an attempt to clarify some issues regarding "d1RSB", "clustering", "freezing", "condensation" in random k-SAT. An effort is made to keep the discussion rather generic and, less successfully, short. This picture originates from statistical physics theories, but we stress results that are known rigorously. References to original literature are mostly not given and this should be fixed at some later point.

=== The setting: ===

* A set of n variables all with the same finite domain of size d, e.g., d=2 in k-SAT.
* A collection of constraints on the variables, each constraint binding k of the n variables, e.g., k=2 in graph coloring.

Typically, the collection consists of "all possible constraints of a certain kind on the n variables", e.g., all <math>2^k \binom{n}{k}</math> clauses of length k in k-SAT, or all <math>\binom{n}{2}</math> edges, i.e., "not equal" constraints, in graph coloring.

* It will be easier to think of the formation of random instances as a "process", in which constraints are added one by one, by selecting one uniformly random constraint from the collection, among those that have not yet been selected (for technical reasons, it often helps to allow selection with replacement, but this turns out to be inconsequential.)
* Finally, it also helps to think of what is called in physics the "energy landscape", i.e., the function counting the number of violated constraints for each value assignment. So, in particular, solutions correspond to the value assignments (points) where the energy is zero.
* For any given problem, let <math>S_n(t)</math> denote the set of solutions of a random instance after t constraints have been added. (Clearly, <math>S_n(t)</math> is a random variable, so everything below refers to the "typical" behavior of <math>S_n</math>.)
* Say that two value assignments are adjacent if they have Hamming distance 1. Under this notion of adjacency, we will look at the "connected components" of <math>S_n</math>, also called "clusters". (Sometimes one replaces "Hamming distance 1" with "subextensive Hamming distance" with no essential difference. This does not seem to be a consequential issue.)

With the above in mind, below is a "voiceover" for the video <math>S_n(0), S_n(1), S_n(2),\ldots</math>.

* Clearly, at t=0, every value assignment is a solution, i.e., <math>S_n(0)</math> is everything, and there is only one cluster.
* Now, fix <math>\delta >0</math> and let <math>X=X(\delta)</math> be the random variable equal to: the smallest number of clusters such that their union contains all but a delta-fraction of <math>S_n</math>.

=== Clustering ===

* It is predicted, for any finite <math>\delta</math>, X undergoes a "phase transition" and goes from 1 to "exponentially many" during the addition of <math>o(n)</math> constraints around a critical, problem-specific constraints-to-variables ratio. The later phase is called clustered. Clustering is a very generic phenomenon for random CSPs.

* Existence of the clustered phase has been rigorously established for random k-SAT, random graph k-coloring, random NAE k-SAT, and a number of other problems, in each case for all values of <math>k > k_0</math> (where <math>k_0</math> is finite and problem dependent) there is a constraint density t/n beyond which <math>S_n(0)</math> is clustered.

* If one thinks in terms of the energy landscape, clustering means that we go from a world with a single big energy-zero valley, to a world with exponentially many smaller energy-zero valleys (and no big energy zero valley).

Of course, to have valleys you need mountains. In particular, another thing that has been rigorously established is that the valleys are "landlocked". Namely:

* For some region of parameters every pair of valleys has Hamming distance <math>\Omega(n)</math>, and every path connecting solutions in distinct valleys, must go through a point in which the energy function has value <math>\Omega(n)</math>. [By the Lipschitzness of the energy function, in fact, the path must go through <math>\Omega(n)</math> such points].

=== 1RSB ===

* 1RSB stands for "1-step Replica Symmetry Breaking". Consider a single variable flip Markov process satisfying the detailed balance condition with respect to uniform distribution over <math>S_n</math> (e.g. Glauber dynamics). Whereas in the "Replica Symmetric" (RS) phase this process is able to sample uniformly <math>S_n</math> in time <math>O(n)</math>, the 1RSB phase is defined as phase where uniform sampling with this process requires time exponential in n.

* The uniform measure over <math>S_n</math> ceases to be an extremal Gibbs measure at the 1RSB transition. In the 1RSB phase <math>S_n</math> is a union of exponentially many extremal Gibbs measures, sometimes called states in physics. The reconstruction problem of graphs is solvable only and only in the d1RSB phase. Equivalence of the three definitions of d1RSB given above in random K-SAT is predicted in statistical physics theories, and is so far proven only partially. Statistical physics theories predict sharp transition from the RS to the d1RSB phase and their locations.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. For the definition of condensation see below.

Note that clustering implies 1RSB but 1RSB does not imply clustering defined as above.

A word of caution: In statistical physics literature clustering is almost always defined via 1RSB, not as above.

=== Freezing===
* The next relevant phenomenon is the emergence of "frozen variables". Concretely, a variable is frozen in a cluster if it takes the same value in all assignments of that cluster. Note that the same variable can be frozen to different values in different clusters and can be frozen in some clusters but not in others. Freezing implies clustering, but clustering can (and does) occur without freezing.

Regarding frozen variables we rigorously know for instance the following:

# For <math>k>k_1</math> there is a constraint density in random K-SAT beyond which a uniformly random solution, with high probability, has <math>\Omega(n)</math> frozen variables.
# As k is increased (which in k-SAT means the length of the clauses, while in coloring the number of colors), the constraint density beyond which emergence of frozen variables is proven agrees in the leading order in k with the constraint density beyond which clustering appears.
# (Perhaps most importantly) It was proven for significantly larger constraint densities that while <math>S_n</math> still consists of "exponentially many clusters of roughly equal size", with high probability, EVERY SINGLE cluster contains <math>\Omega(n)</math> frozen variables. (And indeed, the fraction of variables that are frozen tends to 1 with k.)

To put this a bit more starkly: For a number of random CSP problems, for a sizable fraction of the satisfiable regime of each problem, the space of solutions looks like an "error-correcting code with fuzz". The "fuzz" is the little cloud that forms by jiggling the non-frozen variables. Again, it's important to remember that the set of frozen variables differs from cluster to cluster and that, moreover, a variable can be frozen to different values in different clusters.

* After <math>S_n</math> has reached the above "error-correcting code with fuzz" state, it is clear that every single constraint added from now on will "kill", in expectation, a constant fraction of all clusters (since each cluster has a constant fraction of frozen variables and, therefore, a constant probability of being killed).

=== Condensation ===
* Consider two variables that are far away from each other (in terms of the shortest path between them), the correlation between these two variables is defined as <math>E(x_1 x_2) - E(x_1) E(x_2)</math>, where the average is over the uniform measure over <math>S_n</math>. In the phase called "condensed" the correlation between a typical couple of variables does not go to zero as their distance goes to zero.

* In the condensed phase only a handful (finitely-many-in-expectation) of Gibbs states, capture all but a vanishing fraction of <math>S_n</math>, while exponentially many smaller Gibbs states still exist. In the regime where the rigorous results about clustering and freezing hold the term "Gibbs state" can be interchanged for "cluster" in this statement.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. The d1RSB stands for "dynamic one-step replica symmetry breaking".

=== Random 3-SAT versus large k-SAT ===
* When k is large, it is rigorously known that the 1RSB, clustering and freezing (of most clusters) happens at the same (in the first order in k) constraint density. Whereas the condensation and the satisfiability threshold happen nearby each other and much beyond clustering. And no algorithm has been known to work in the clustered phase -- an open problem for more than 30 years.

* The situation is crucially different when k is small. In 3-SAT (and also 3-COL) for instance statistical physics predicts that the 1RSB and condensation transition coincide. Hence there is no d1RSB phase. And the freezing happens relatively nearby to the satisfiability threshold. In 3-coloring the 1RSB threshold is when every variable has on average 4 neighbors. Whereas polynomial algorithms are known to work rigorously up to 4.03.

=== Locked constraint satisfaction problems ===
* Fortunately there are NP-complete CSPs where the description of the space of solutions is much simpler than in random K-SAT. In the random locked CSP's 1RSB, clustering and freezing transitions coincide. And no condensed phase exists.

* Consider for instance k-in-2k SAT, that is each clause contains 2k variables and is satisfied if and only if k of the variables are TRUE and k are FALSE (no negations present). And consider every variable being included in at least 3 clauses. Then the space of solutions consists of single configurations separated by extensive Hamming distance in the whole satisfiable region.

=== Where the hard instances are? ===
* The empirical finding that hardest k-SAT instances are around the satisfiability threshold is well known but not precise. The example of 3-coloring testifies that neither the 1RSB not the condensation in the space of solutions pose general algorithmic barriers. On the other hand no polynomial algorithm is known to work (not even empirically) in any of the NP-complete problems in the phase where ALL clusters are frozen.

=== Random k-XOR-SAT ===
Finally, what about random k-XOR-SAT ?

* First, a technical point. If one does indeed generate instances by selecting the variables in each constraint uniformly at random (without insisting that each variable has degree at least 2 as one does in LDPC codes), then there will be variables which appears in 0 or 1 constraints. Clearly, such variables can be "repeatedly removed" leaving a "core" structure. It is clear that if one finds a solution to the core, then this solution can be trivially extended to the rest. OK, what about solutions to this core?
* Well, this core does indeed behave like -- you guessed it -- an error-correcting code, indeed one with absolutely no fuzz: each connected component has size 1. Intuitively, the reason is that if one is at a "codeword" and changes the value of a single variable V, since we are dealing with parity constraints, this will require flipping some other variable in each of the constraints that contain V, and since the underlying (hyper-/factor)graph is an expander, such "forced changes" will proliferate. Note that such a proliferation does not necessarily occur in random k-SAT or graph coloring, as it's possible to change a single variable and still have every constraint be satisfied. This "redundancy" in the solutions is precisely what gives rise to the aforementioned "fuzz" for those problems.
* Finally, the heart of the matter, and what I believe is meant by Deolalikar when he speaks of "independent parameters". The cores/codewords in random k-XOR-SAT, are linearly related. In contrast, in random k-SAT we have no reason to think that they should be and one can, indeed, think of them as (more or less) randomly placed points inside the set of all value assignments, thus requiring "many" parameters to be specified. Alternatively, one can think of the random CSP instances as taking the randomness used to define the factor graph of the instance and "lifting it" to the high-dimensional space of solutions, by creating "randomly placed" pockets of solutions (clusters).

== References ==

* [CKT91] [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.97.3555&rep=rep1&type=pdf Where the Really Hard Problems Are ?], P Cheeseman, B Kanefsky, WM Taylor, Proccedings IJCAI-91, 1991, 163-169.

Random k-SAT

2010-08-11T20:44:21Z

Krzakala:

Below are some notes of Dimitris Achlioptas, with additions from Lenka Zdeborova.

This is an attempt to clarify some issues regarding "d1RSB", "clustering", "freezing", "condensation" in random k-SAT. An effort is made to keep the discussion rather generic and, less successfully, short. This picture originates from statistical physics theories, but we stress results that are known rigorously. References to original literature are mostly not given and this should be fixed at some later point.

=== The setting: ===

* A set of n variables all with the same finite domain of size d, e.g., d=2 in k-SAT.
* A collection of constraints on the variables, each constraint binding k of the n variables, e.g., k=2 in graph coloring.

Typically, the collection consists of "all possible constraints of a certain kind on the n variables", e.g., all <math>2^k \binom{n}{k}</math> clauses of length k in k-SAT, or all <math>\binom{n}{2}</math> edges, i.e., "not equal" constraints, in graph coloring.

* It will be easier to think of the formation of random instances as a "process", in which constraints are added one by one, by selecting one uniformly random constraint from the collection, among those that have not yet been selected (for technical reasons, it often helps to allow selection with replacement, but this turns out to be inconsequential.)
* Finally, it also helps to think of what is called in physics the "energy landscape", i.e., the function counting the number of violated constraints for each value assignment. So, in particular, solutions correspond to the value assignments (points) where the energy is zero.
* For any given problem, let <math>S_n(t)</math> denote the set of solutions of a random instance after t constraints have been added. (Clearly, <math>S_n(t)</math> is a random variable, so everything below refers to the "typical" behavior of <math>S_n</math>.)
* Say that two value assignments are adjacent if they have Hamming distance 1. Under this notion of adjacency, we will look at the "connected components" of <math>S_n</math>, also called "clusters". (Sometimes one replaces "Hamming distance 1" with "subextensive Hamming distance" with no essential difference. This does not seem to be a consequential issue.)

With the above in mind, below is a "voiceover" for the video <math>S_n(0), S_n(1), S_n(2),\ldots</math>.

* Clearly, at t=0, every value assignment is a solution, i.e., <math>S_n(0)</math> is everything, and there is only one cluster.
* Now, fix <math>\delta >0</math> and let <math>X=X(\delta)</math> be the random variable equal to: the smallest number of clusters such that their union contains all but a delta-fraction of <math>S_n</math>.

=== Clustering ===

* It is predicted, for any finite <math>\delta</math>, X undergoes a "phase transition" and goes from 1 to "exponentially many" during the addition of <math>o(n)</math> constraints around a critical, problem-specific constraints-to-variables ratio. The later phase is called clustered. Clustering is a very generic phenomenon for random CSPs.

* Existence of the clustered phase has been rigorously established for random k-SAT, random graph k-coloring, random NAE k-SAT, and a number of other problems, in each case for all values of <math>k > k_0</math> (where <math>k_0</math> is finite and problem dependent) there is a constraint density t/n beyond which <math>S_n(0)</math> is clustered.

* If one thinks in terms of the energy landscape, clustering means that we go from a world with a single big energy-zero valley, to a world with exponentially many smaller energy-zero valleys (and no big energy zero valley).

Of course, to have valleys you need mountains. In particular, another thing that has been rigorously established is that the valleys are "landlocked". Namely:

* For some region of parameters every pair of valleys has Hamming distance <math>\Omega(n)</math>, and every path connecting solutions in distinct valleys, must go through a point in which the energy function has value <math>\Omega(n)</math>. [By the Lipschitzness of the energy function, in fact, the path must go through <math>\Omega(n)</math> such points].

=== 1RSB ===

* 1RSB stands for "1-step Replica Symmetry Breaking". Consider a single variable flip Markov process satisfying the detailed balance condition with respect to uniform distribution over <math>S_n</math> (e.g. Glauber dynamics). Whereas in the "Replica Symmetric" (RS) phase this process is able to sample uniformly <math>S_n</math> in time <math>O(n)</math>, the 1RSB phase is defined as phase where uniform sampling with this process requires time exponential in n.

* The uniform measure over <math>S_n</math> ceases to be an extremal Gibbs measure at the 1RSB transition. In the 1RSB phase <math>S_n</math> is a union of exponentially many extremal Gibbs measures, sometimes called states in physics. The reconstruction problem of graphs is solvable only and only in the d1RSB phase. Equivalence of the three definitions of d1RSB given above in random K-SAT is predicted in statistical physics theories, and is so far proven only partially. Statistical physics theories predict sharp transition from the RS to the d1RSB phase and their locations.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. For the definition of condensation see below.

Note that clustering implies 1RSB but 1RSB does not imply clustering defined as above.

A word of caution: In statistical physics literature clustering is almost always defined via 1RSB, not as above.

=== Freezing===
* The next relevant phenomenon is the emergence of "frozen variables". Concretely, a variable is frozen in a cluster if it takes the same value in all assignments of that cluster. Note that the same variable can be frozen to different values in different clusters and can be frozen in some clusters but not in others. Freezing implies clustering, but clustering can (and does) occur without freezing.

Regarding frozen variables we rigorously know for instance the following:

# For <math>k>k_1</math> there is a constraint density in random K-SAT beyond which a uniformly random solution, with high probability, has <math>\Omega(n)</math> frozen variables.
# As k is increased (which in k-SAT means the length of the clauses, while in coloring the number of colors), the constraint density beyond which emergence of frozen variables is proven agrees in the leading order in k with the constraint density beyond which clustering appears.
# (Perhaps most importantly) It was proven for significantly larger constraint densities that while <math>S_n</math> still consists of "exponentially many clusters of roughly equal size", with high probability, EVERY SINGLE cluster contains <math>\Omega(n)</math> frozen variables. (And indeed, the fraction of variables that are frozen tends to 1 with k.)

To put this a bit more starkly: For a number of random CSP problems, for a sizable fraction of the satisfiable regime of each problem, the space of solutions looks like an "error-correcting code with fuzz". The "fuzz" is the little cloud that forms by jiggling the non-frozen variables. Again, it's important to remember that the set of frozen variables differs from cluster to cluster and that, moreover, a variable can be frozen to different values in different clusters.

* After <math>S_n</math> has reached the above "error-correcting code with fuzz" state, it is clear that every single constraint added from now on will "kill", in expectation, a constant fraction of all clusters (since each cluster has a constant fraction of frozen variables and, therefore, a constant probability of being killed).

=== Condensation ===
* Consider two variables that are far away from each other (in terms of the shortest path between them), the correlation between these two variables is defined as <math>E(x_1 x_2) - E(x_1) E(x_2)</math>, where the average is over the uniform measure over <math>S_n</math>. In the phase called "condensed" the correlation between a typical couple of variables does not go to zero as their distance goes to zero.

* In the condensed phase only a handful (finitely-many-in-expectation) of Gibbs states, capture all but a vanishing fraction of <math>S_n</math>, while exponentially many smaller Gibbs states still exist. In the regime where the rigorous results about clustering and freezing hold the term "Gibbs state" can be interchanged for "cluster" in this statement.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. The d1RSB stands for "dynamic one-step replica symmetry breaking".

=== Random 3-SAT versus large k-SAT ===
* When k is large, it is rigorously known that the 1RSB, clustering and freezing (of most clusters) happens at the same (in the first order in k) constraint density. Whereas the condensation and the satisfiability threshold happen nearby each other and much beyond clustering. And no algorithm has been known to work in the clustered phase -- an open problem for more than 30 years.

* The situation is crucially different when k is small. In 3-SAT (and also 3-COL) for instance statistical physics predicts that the 1RSB and condensation transition coincide. Hence there is no d1RSB phase. And the freezing happens relatively nearby to the satisfiability threshold. In 3-coloring the 1RSB threshold is when every variable has on average 4 neighbors. Whereas polynomial algorithms are known to work rigorously up to 4.03.

=== Locked constraint satisfaction problems ===
* Fortunately there are NP-complete CSPs where the description of the space of solutions is much simpler than in random K-SAT. In the random locked CSP's 1RSB, clustering and freezing transitions coincide. And no condensed phase exists.

* Consider for instance k-in-2k SAT, that is each clause contains 2k variables and is satisfied if and only if k of the variables are TRUE and k are FALSE (no negations present). And consider every variable being included in at least 3 clauses. Then the space of solutions consists of single configurations separated by extensive Hamming distance in the whole satisfiable region.

=== Where the hard instances are? ===
* The empirical finding that hardest k-SAT instances are around the satisfiability threshold is well known but not precise. The example of 3-coloring testifies that neither the 1RSB not the condensation in the space of solutions pose general algorithmic barriers. On the other hand no polynomial algorithm is known to work (not even empirically) in any of the NP-complete problems in the phase where ALL clusters are frozen.

=== Random k-XOR-SAT ===
Finally, what about random k-XOR-SAT ?

* First, a technical point. If one does indeed generate instances by selecting the variables in each constraint uniformly at random (without insisting that each variable has degree at least 2 as one does in LDPC codes), then there will be variables which appears in 0 or 1 constraints. Clearly, such variables can be "repeatedly removed" leaving a "core" structure. It is clear that if one finds a solution to the core, then this solution can be trivially extended to the rest. OK, what about solutions to this core?
* Well, this core does indeed behave like -- you guessed it -- an error-correcting code, indeed one with absolutely no fuzz: each connected component has size 1. Intuitively, the reason is that if one is at a "codeword" and changes the value of a single variable V, since we are dealing with parity constraints, this will require flipping some other variable in each of the constraints that contain V, and since the underlying (hyper-/factor)graph is an expander, such "forced changes" will proliferate. Note that such a proliferation does not necessarily occur in random k-SAT or graph coloring, as it's possible to change a single variable and still have every constraint be satisfied. This "redundancy" in the solutions is precisely what gives rise to the aforementioned "fuzz" for those problems.
* Finally, the heart of the matter, and what I believe is meant by Deolalikar when he speaks of "independent parameters". The cores/codewords in random k-XOR-SAT, are linearly related. In contrast, in random k-SAT we have no reason to think that they should be and one can, indeed, think of them as (more or less) randomly placed points inside the set of all value assignments, thus requiring "many" parameters to be specified. Alternatively, one can think of the random CSP instances as taking the randomness used to define the factor graph of the instance and "lifting it" to the high-dimensional space of solutions, by creating "randomly placed" pockets of solutions (clusters).

== References ==
{{reflist}}

Random k-SAT

2010-08-11T20:43:48Z

Krzakala:

Below are some notes of Dimitris Achlioptas, with additions from Lenka Zdeborova.

This is an attempt to clarify some issues regarding "d1RSB", "clustering", "freezing", "condensation" in random k-SAT. An effort is made to keep the discussion rather generic and, less successfully, short. This picture originates from statistical physics theories, but we stress results that are known rigorously. References to original literature are mostly not given and this should be fixed at some later point. <ref name="Pearl-88">
{{cite book
|last1=Pearl |first1=Judea |authorlink1=Judea Pearl
|year=1988
|title=Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
|edition=2nd
|location=San Francisco, CA |publisher=Morgan Kaufmann
|isbn=1558604790
}}
</ref>

=== The setting: ===

* A set of n variables all with the same finite domain of size d, e.g., d=2 in k-SAT.
* A collection of constraints on the variables, each constraint binding k of the n variables, e.g., k=2 in graph coloring.

Typically, the collection consists of "all possible constraints of a certain kind on the n variables", e.g., all <math>2^k \binom{n}{k}</math> clauses of length k in k-SAT, or all <math>\binom{n}{2}</math> edges, i.e., "not equal" constraints, in graph coloring.

* It will be easier to think of the formation of random instances as a "process", in which constraints are added one by one, by selecting one uniformly random constraint from the collection, among those that have not yet been selected (for technical reasons, it often helps to allow selection with replacement, but this turns out to be inconsequential.)
* Finally, it also helps to think of what is called in physics the "energy landscape", i.e., the function counting the number of violated constraints for each value assignment. So, in particular, solutions correspond to the value assignments (points) where the energy is zero.
* For any given problem, let <math>S_n(t)</math> denote the set of solutions of a random instance after t constraints have been added. (Clearly, <math>S_n(t)</math> is a random variable, so everything below refers to the "typical" behavior of <math>S_n</math>.)
* Say that two value assignments are adjacent if they have Hamming distance 1. Under this notion of adjacency, we will look at the "connected components" of <math>S_n</math>, also called "clusters". (Sometimes one replaces "Hamming distance 1" with "subextensive Hamming distance" with no essential difference. This does not seem to be a consequential issue.)

With the above in mind, below is a "voiceover" for the video <math>S_n(0), S_n(1), S_n(2),\ldots</math>.

* Clearly, at t=0, every value assignment is a solution, i.e., <math>S_n(0)</math> is everything, and there is only one cluster.
* Now, fix <math>\delta >0</math> and let <math>X=X(\delta)</math> be the random variable equal to: the smallest number of clusters such that their union contains all but a delta-fraction of <math>S_n</math>.

=== Clustering ===

* It is predicted, for any finite <math>\delta</math>, X undergoes a "phase transition" and goes from 1 to "exponentially many" during the addition of <math>o(n)</math> constraints around a critical, problem-specific constraints-to-variables ratio. The later phase is called clustered. Clustering is a very generic phenomenon for random CSPs.

* Existence of the clustered phase has been rigorously established for random k-SAT, random graph k-coloring, random NAE k-SAT, and a number of other problems, in each case for all values of <math>k > k_0</math> (where <math>k_0</math> is finite and problem dependent) there is a constraint density t/n beyond which <math>S_n(0)</math> is clustered.

* If one thinks in terms of the energy landscape, clustering means that we go from a world with a single big energy-zero valley, to a world with exponentially many smaller energy-zero valleys (and no big energy zero valley).

Of course, to have valleys you need mountains. In particular, another thing that has been rigorously established is that the valleys are "landlocked". Namely:

* For some region of parameters every pair of valleys has Hamming distance <math>\Omega(n)</math>, and every path connecting solutions in distinct valleys, must go through a point in which the energy function has value <math>\Omega(n)</math>. [By the Lipschitzness of the energy function, in fact, the path must go through <math>\Omega(n)</math> such points].

=== 1RSB ===

* 1RSB stands for "1-step Replica Symmetry Breaking". Consider a single variable flip Markov process satisfying the detailed balance condition with respect to uniform distribution over <math>S_n</math> (e.g. Glauber dynamics). Whereas in the "Replica Symmetric" (RS) phase this process is able to sample uniformly <math>S_n</math> in time <math>O(n)</math>, the 1RSB phase is defined as phase where uniform sampling with this process requires time exponential in n.

* The uniform measure over <math>S_n</math> ceases to be an extremal Gibbs measure at the 1RSB transition. In the 1RSB phase <math>S_n</math> is a union of exponentially many extremal Gibbs measures, sometimes called states in physics. The reconstruction problem of graphs is solvable only and only in the d1RSB phase. Equivalence of the three definitions of d1RSB given above in random K-SAT is predicted in statistical physics theories, and is so far proven only partially. Statistical physics theories predict sharp transition from the RS to the d1RSB phase and their locations.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. For the definition of condensation see below.

Note that clustering implies 1RSB but 1RSB does not imply clustering defined as above.

A word of caution: In statistical physics literature clustering is almost always defined via 1RSB, not as above.

=== Freezing===
* The next relevant phenomenon is the emergence of "frozen variables". Concretely, a variable is frozen in a cluster if it takes the same value in all assignments of that cluster. Note that the same variable can be frozen to different values in different clusters and can be frozen in some clusters but not in others. Freezing implies clustering, but clustering can (and does) occur without freezing.

Regarding frozen variables we rigorously know for instance the following:

# For <math>k>k_1</math> there is a constraint density in random K-SAT beyond which a uniformly random solution, with high probability, has <math>\Omega(n)</math> frozen variables.
# As k is increased (which in k-SAT means the length of the clauses, while in coloring the number of colors), the constraint density beyond which emergence of frozen variables is proven agrees in the leading order in k with the constraint density beyond which clustering appears.
# (Perhaps most importantly) It was proven for significantly larger constraint densities that while <math>S_n</math> still consists of "exponentially many clusters of roughly equal size", with high probability, EVERY SINGLE cluster contains <math>\Omega(n)</math> frozen variables. (And indeed, the fraction of variables that are frozen tends to 1 with k.)

To put this a bit more starkly: For a number of random CSP problems, for a sizable fraction of the satisfiable regime of each problem, the space of solutions looks like an "error-correcting code with fuzz". The "fuzz" is the little cloud that forms by jiggling the non-frozen variables. Again, it's important to remember that the set of frozen variables differs from cluster to cluster and that, moreover, a variable can be frozen to different values in different clusters.

* After <math>S_n</math> has reached the above "error-correcting code with fuzz" state, it is clear that every single constraint added from now on will "kill", in expectation, a constant fraction of all clusters (since each cluster has a constant fraction of frozen variables and, therefore, a constant probability of being killed).

=== Condensation ===
* Consider two variables that are far away from each other (in terms of the shortest path between them), the correlation between these two variables is defined as <math>E(x_1 x_2) - E(x_1) E(x_2)</math>, where the average is over the uniform measure over <math>S_n</math>. In the phase called "condensed" the correlation between a typical couple of variables does not go to zero as their distance goes to zero.

* In the condensed phase only a handful (finitely-many-in-expectation) of Gibbs states, capture all but a vanishing fraction of <math>S_n</math>, while exponentially many smaller Gibbs states still exist. In the regime where the rigorous results about clustering and freezing hold the term "Gibbs state" can be interchanged for "cluster" in this statement.

* d1RSB is a statistical physics term for a 1RSB phase that is not condensed. The d1RSB stands for "dynamic one-step replica symmetry breaking".

=== Random 3-SAT versus large k-SAT ===
* When k is large, it is rigorously known that the 1RSB, clustering and freezing (of most clusters) happens at the same (in the first order in k) constraint density. Whereas the condensation and the satisfiability threshold happen nearby each other and much beyond clustering. And no algorithm has been known to work in the clustered phase -- an open problem for more than 30 years.

* The situation is crucially different when k is small. In 3-SAT (and also 3-COL) for instance statistical physics predicts that the 1RSB and condensation transition coincide. Hence there is no d1RSB phase. And the freezing happens relatively nearby to the satisfiability threshold. In 3-coloring the 1RSB threshold is when every variable has on average 4 neighbors. Whereas polynomial algorithms are known to work rigorously up to 4.03.

=== Locked constraint satisfaction problems ===
* Fortunately there are NP-complete CSPs where the description of the space of solutions is much simpler than in random K-SAT. In the random locked CSP's 1RSB, clustering and freezing transitions coincide. And no condensed phase exists.

* Consider for instance k-in-2k SAT, that is each clause contains 2k variables and is satisfied if and only if k of the variables are TRUE and k are FALSE (no negations present). And consider every variable being included in at least 3 clauses. Then the space of solutions consists of single configurations separated by extensive Hamming distance in the whole satisfiable region.

=== Where the hard instances are? ===
* The empirical finding that hardest k-SAT instances are around the satisfiability threshold is well known but not precise. The example of 3-coloring testifies that neither the 1RSB not the condensation in the space of solutions pose general algorithmic barriers. On the other hand no polynomial algorithm is known to work (not even empirically) in any of the NP-complete problems in the phase where ALL clusters are frozen.

=== Random k-XOR-SAT ===
Finally, what about random k-XOR-SAT ?

* First, a technical point. If one does indeed generate instances by selecting the variables in each constraint uniformly at random (without insisting that each variable has degree at least 2 as one does in LDPC codes), then there will be variables which appears in 0 or 1 constraints. Clearly, such variables can be "repeatedly removed" leaving a "core" structure. It is clear that if one finds a solution to the core, then this solution can be trivially extended to the rest. OK, what about solutions to this core?
* Well, this core does indeed behave like -- you guessed it -- an error-correcting code, indeed one with absolutely no fuzz: each connected component has size 1. Intuitively, the reason is that if one is at a "codeword" and changes the value of a single variable V, since we are dealing with parity constraints, this will require flipping some other variable in each of the constraints that contain V, and since the underlying (hyper-/factor)graph is an expander, such "forced changes" will proliferate. Note that such a proliferation does not necessarily occur in random k-SAT or graph coloring, as it's possible to change a single variable and still have every constraint be satisfied. This "redundancy" in the solutions is precisely what gives rise to the aforementioned "fuzz" for those problems.
* Finally, the heart of the matter, and what I believe is meant by Deolalikar when he speaks of "independent parameters". The cores/codewords in random k-XOR-SAT, are linearly related. In contrast, in random k-SAT we have no reason to think that they should be and one can, indeed, think of them as (more or less) randomly placed points inside the set of all value assignments, thus requiring "many" parameters to be specified. Alternatively, one can think of the random CSP instances as taking the randomness used to define the factor graph of the instance and "lifting it" to the high-dimensional space of solutions, by creating "randomly placed" pockets of solutions (clusters).

== References ==
{{reflist}}

Deolalikar P vs NP paper

2010-08-10T19:01:19Z

Krzakala: Issues with XOR-SAT

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

This is a clearinghouse wiki page for the analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP, and to aggregate various pieces of news and information about this paper. Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions or speculations are to be avoided. This page is derived from an [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].

For the latest discussion on the technical points of the paper, see [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ this thread of Dick Lipton and Ken Regan]. For meta-discussion of this wiki (and other non-mathematical or meta-mathematical issues), see [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html this thread of Suresh Venkatasubramanian].

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

== Typos and minor errors ==

* (Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via [http://scottaaronson.com/blog/?p=456#comment-44783 Blake Stacey])
* (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])
* (Second draft, page 27) <math>n 2^n</math> independent parameters → <math> n 2^k</math> independent parameters

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

== Possible issues ==

=== Issues with LFP ===
There appear to be three issues related to the use of the characterization of P in terms of first order logic, an ordering and a least fixed point operator. All of these are discussed in the [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, and Arthur Milchior.

# Is the lack of ordering in the logical structures used to define the LFP structure a problem ? On the surface, it appears to be, since it is not known whether FO(LFP) can be used to characterize P without ordering. (No, it is known that parity can not be expressed without an ordering even with LFP, hence P is not captured without order [[http://portal.acm.org/citation.cfm?id=256295 AVV1997, page 35]]. But 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> )
# 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.
# Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?

=== Issues with random k-SAT ===

# '''The nomenclature of phase transitions''': In the statistical physics picture, there is not a single phase transition, but rather a set of different transitions called "clustering", "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 paper, clustering and freezing are mixed-up.
# '''Whether the "clustering" or the "condensation" stages are significant ''': the latest ideas from physics suggest that random <math>k</math>-SAT and similar CSPs don’t become hard at the clustering transition, as was previously believed, and that the condensation transition is not connected to hardness either. 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 compare the performance of algorithms] with the [http://arxiv.org/abs/0704.1269 statistical physics predictions.]
# '''Whether the "freezing" stage is significant ''': It was thus [http://arxiv.org/abs/0704.1269 more recently 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 after the freezing transition so that k-SAT is hard in the region where w.h.p. all clusters have frozen variables. Such a region is known to exist rigorously.
# '''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]).
# '''Whether a complex solution space amounts to true problem hardness''': The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". There are two "meta" objections to this. 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. ''Any objections to these objections are welcome!''
## Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]). 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. That is, the fact that random k-SAT has a "hard" distribution of solutions does not seem to be relevant for showing that k-SAT is hard. That is, it is not sufficient to use a problem with a hard distribution of solutions, if you're separating P from NP.
## Moreover, a hard distribution of solutions is not necessary for NP-hardness, either. The "hard" case of 3-SAT is the case where there is *at most one* satisfying assignment. 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? Suppose Valiant-Vazirani can be derandomized to run in deterministic polynomial time (which is true if plausible circuit lower bounds hold up). For every LFP formula F that is to solve k-SAT, replace it with an LFP formula F' that has computationally equivalent behavior to the following algorithm: first "Valiant-Vazirani-ize" your input formula (reduce it to having at most one solution in polynomial time) then evaluate F on the result. These new formulas only have at most "one" solution to deal with. The intuition here is that either Valiant-Vazirani can't be derandomized (very unlikely) or the proof must break (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]). But again, this is just intuition.

=== Barriers ===

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

==== Relativization ====

==== Natural proofs ====

==== Algebraization ====

== Terminology ==

* [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, Godel'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, Godel'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 (aggregates all 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

=== Media and aggregators ===

* [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.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

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

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

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].

== 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, Complexity of Relational Query Languages, 14th Symposium on Theory of Computation (1982), 137-146.

== Other links ==

* [http://en.wikipedia.org/wiki/P_%3D_NP_problem P versus NP problem] - Wikipedia
* [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]

Deolalikar P vs NP paper

2010-08-10T19:00:32Z

Krzakala: Issues with XOR-SAT

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

This is a clearinghouse wiki page for the analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP, and to aggregate various pieces of news and information about this paper. Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions or speculations are to be avoided. This page is derived from an [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].

For the latest discussion on the technical points of the paper, see [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ this thread of Dick Lipton and Ken Regan]. For meta-discussion of this wiki (and other non-mathematical or meta-mathematical issues), see [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html this thread of Suresh Venkatasubramanian].

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

== Typos and minor errors ==

* (Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via [http://scottaaronson.com/blog/?p=456#comment-44783 Blake Stacey])
* (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])
* (Second draft, page 27) <math>n 2^n</math> independent parameters → <math> n 2^k</math> independent parameters

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

== Possible issues ==

=== Issues with LFP ===
There appear to be three issues related to the use of the characterization of P in terms of first order logic, an ordering and a least fixed point operator. All of these are discussed in the [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, and Arthur Milchior.

# Is the lack of ordering in the logical structures used to define the LFP structure a problem ? On the surface, it appears to be, since it is not known whether FO(LFP) can be used to characterize P without ordering. (No, it is known that parity can not be expressed without an ordering even with LFP, hence P is not captured without order [[http://portal.acm.org/citation.cfm?id=256295 AVV1997, page 35]]. But 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> )
# 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.
# Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?

=== Issues with random k-SAT ===

# '''The nomenclature of phase transitions''': In the statistical physics picture, there is not a single phase transition, but rather a set of different transitions called "clustering", "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 paper, clustering and freezing are mixed-up.
# '''Whether the "clustering" or the "condensation" stages are significant ''': the latest ideas from physics suggest that random <math>k</math>-SAT and similar CSPs don’t become hard at the clustering transition, as was previously believed, and that the condensation transition is not connected to hardness either. 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 compare the performance of algorithms] with the [http://arxiv.org/abs/0704.1269 statistical physics predictions.]
# '''Whether the "freezing" stage is significant ''': It was thus [http://arxiv.org/abs/0704.1269 more recently 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 after the freezing transition so that k-SAT is hard in the region where w.h.p. all clusters have frozen variables. Such a region is known to exist rigorously.
# '''The XOR-SAT objection ''': The conjecture that frozen variable makes 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]).
# '''Whether a complex solution space amounts to true problem hardness''': The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". There are two "meta" objections to this. 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. ''Any objections to these objections are welcome!''
## Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]). 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. That is, the fact that random k-SAT has a "hard" distribution of solutions does not seem to be relevant for showing that k-SAT is hard. That is, it is not sufficient to use a problem with a hard distribution of solutions, if you're separating P from NP.
## Moreover, a hard distribution of solutions is not necessary for NP-hardness, either. The "hard" case of 3-SAT is the case where there is *at most one* satisfying assignment. 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? Suppose Valiant-Vazirani can be derandomized to run in deterministic polynomial time (which is true if plausible circuit lower bounds hold up). For every LFP formula F that is to solve k-SAT, replace it with an LFP formula F' that has computationally equivalent behavior to the following algorithm: first "Valiant-Vazirani-ize" your input formula (reduce it to having at most one solution in polynomial time) then evaluate F on the result. These new formulas only have at most "one" solution to deal with. The intuition here is that either Valiant-Vazirani can't be derandomized (very unlikely) or the proof must break (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]). But again, this is just intuition.

=== Barriers ===

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

==== Relativization ====

==== Natural proofs ====

==== Algebraization ====

== Terminology ==

* [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, Godel'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, Godel'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 (aggregates all 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

=== Media and aggregators ===

* [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.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

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

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

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].

== 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, Complexity of Relational Query Languages, 14th Symposium on Theory of Computation (1982), 137-146.

== Other links ==

* [http://en.wikipedia.org/wiki/P_%3D_NP_problem P versus NP problem] - Wikipedia
* [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]

Deolalikar P vs NP paper

2010-08-10T17:46:59Z

Krzakala: Issues with random k-SAT and the statistical physics picture

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

This is a clearinghouse wiki page for the analysis of Vinay Deolalikar's recent preprint claiming to prove that P != NP, and to aggregate various pieces of news and information about this paper. Corrections and new contributions to this page are definitely welcome. Of course, any new material should be sourced whenever possible, and remain constructive and objectively neutral; in particular, personal subjective opinions or speculations are to be avoided. This page is derived from an [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].

For the latest discussion on the technical points of the paper, see [http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ this thread of Dick Lipton and Ken Regan]. For meta-discussion of this wiki (and other non-mathematical or meta-mathematical issues), see [http://geomblog.blogspot.com/2010/08/polymath-home-for-analysis-of.html this thread of Suresh Venkatasubramanian].

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

== Typos and minor errors ==

* (Second draft, page 31, Definition 2.16): "Perfect man" should be "Perfect map". (via [http://scottaaronson.com/blog/?p=456#comment-44783 Blake Stacey])
* (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])
* (Second draft, page 27) <math>n 2^n</math> independent parameters → <math> n 2^k</math> independent parameters

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

== Possible issues ==

=== Issues with LFP ===
There appear to be three issues related to the use of the characterization of P in terms of first order logic, an ordering and a least fixed point operator. All of these are discussed in the [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, and Arthur Milchior.

# Is the lack of ordering in the logical structures used to define the LFP structure a problem ? On the surface, it appears to be, since it is not known whether FO(LFP) can be used to characterize P without ordering. (No, it is known that parity can not be expressed without an ordering even with LFP, hence P is not captured without order [[http://portal.acm.org/citation.cfm?id=256295 AVV1997, page 35]]. But 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> )
# 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.
# Does the logical vocabulary created to express the LFP operation suffice to capture all P-time operations ?

=== Issues with random k-SAT ===

# '''The nomenclature of phase transitions''': In the statistical physics picture, there is not a single phase transition, but rather a set of different transitions called "clustering", "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 paper, clustering and freezing are mixed-up.
# '''Whether the "clustering" or the "condensation" stages are significant ''': the latest ideas from physics suggest that random <math>k</math>-SAT and similar CSPs don’t become hard at the clustering transition, as was previously believed, and that the condensation transition is not connected to hardness either. 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 compare the performance of algorithms] with the [http://arxiv.org/abs/0704.1269 statistical physics predictions.]
# '''Whether the "freezing" stage is significant ''': It was thus [http://arxiv.org/abs/0704.1269 more recently 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 after the freezing transition so that k-SAT is hard in the region where w.h.p. all clusters have frozen variables. Such a region is known to exist rigorously. Note however that random k-XORSAT has a clustering transition, frozen variables, etc., but is of course in P. ([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])
# '''Whether a complex solution space amounts to true problem hardness''': The author tries to use the fact that for certain distributions of random k-SAT, the solution space has a "hard structure". There are two "meta" objections to this. 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. ''Any objections to these objections are welcome!''
## Polytime solvable problems (such as perfect matching on random graphs) can also have complicated solution distributions (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]). 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. That is, the fact that random k-SAT has a "hard" distribution of solutions does not seem to be relevant for showing that k-SAT is hard. That is, it is not sufficient to use a problem with a hard distribution of solutions, if you're separating P from NP.
## Moreover, a hard distribution of solutions is not necessary for NP-hardness, either. The "hard" case of 3-SAT is the case where there is *at most one* satisfying assignment. 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? Suppose Valiant-Vazirani can be derandomized to run in deterministic polynomial time (which is true if plausible circuit lower bounds hold up). For every LFP formula F that is to solve k-SAT, replace it with an LFP formula F' that has computationally equivalent behavior to the following algorithm: first "Valiant-Vazirani-ize" your input formula (reduce it to having at most one solution in polynomial time) then evaluate F on the result. These new formulas only have at most "one" solution to deal with. The intuition here is that either Valiant-Vazirani can't be derandomized (very unlikely) or the proof must break (Ryan Williams, on [http://twitter.com/rrwilliams/status/20741046788 twitter]). But again, this is just intuition.

=== Barriers ===

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

==== Relativization ====

==== Natural proofs ====

==== Algebraization ====

== Terminology ==

* [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, Godel'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, Godel'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 (aggregates all 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

=== Media and aggregators ===

* [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.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

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

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

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 does no longer appear 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, Complexity of Relational Query Languages, 14th Symposium on Theory of Computation (1982), 137-146.

== Other links ==

* [http://en.wikipedia.org/wiki/P_%3D_NP_problem P versus NP problem] - Wikipedia
* [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]