Gibbs states and the set of solutions of random constraint satisfaction problems

doi:10.1073/pnas.0703685104

Gibbs states and the set of solutions of random constraint satisfaction problems

^aLaboratoire de Physico-Chimie Théorique, Ecole Supérieure de Physique et de Chimie Industrielles, 75005 Paris, France,
^bDepartments of Electrical Engineering and Statistics, Stanford University, CA 94305;
^cLaboratoire de Physique Théorique, Ecole Normale Supérieure, Université Pierre et Marie Curie, 75005 Paris, France;
^eDipartimento di Fisica and Consiglio Nazionale delle Ricerche–Istituto Nazionale per la Fisica della Materia, Università di Roma “La Sapienza,” I-00185 Rome, Italy; and
^fLaboratoire de Physique Théorique et Modèles Statistiques, Université de Paris-Sud, 91405 Orsay, France

Communicated by Giorgio Parisi, University of Rome, Rome, Italy, April 25, 2007 (received for review November 29, 2006)

Abstract

An instance of a random constraint satisfaction problem defines a random subset 𝒮 (the set of solutions) of a large product space X ^N (the set of assignments). We consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs) and study the uniform measure with support on S. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states (“clusters”) and subsequently condensates over the largest such states. Above the condensation point, the mass carried by the n largest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine their precise location. Further, we provide a formal definition of each phase transition in terms of different notions of correlation between distinct variables in the problem. The degree of correlation naturally affects the performances of many search/sampling algorithms. Empirical evidence suggests that local Monte Carlo Markov chain strategies are effective up to the clustering phase transition and belief propagation up to the condensation point. Finally, refined message passing techniques (such as survey propagation) may also beat this threshold.

Footnotes

^dTo whom correspondence should be addressed. E-mail: montanari{at}stanford.edu
Author contributions: F.K., A.M., F.R.-T., G.S., and L.Z. designed research, performed research, contributed new reagents/analytic tools, analyzed data, and wrote the paper.
The authors declare no conflict of interest.
↵ g For coloring l-regular graphs, we can use l = 2α as a parameter. When considering a phase transition defined through some property 𝒫 increasing in l, we adopt the convention of denoting its location through the smallest integer such that 𝒫 holds.
↵ h The term “with high probability” means with probability approaching one as N → ∞.
↵ i One possible approach to the definition of a Monte Carlo Markov chain algorithm is to relax the constraints by setting ψ_a(⋯) = ϵ instead of 0 whenever the ath constraint is violated. Glauber dynamics can then be used to sample from the relaxed measure μ_ϵ .
↵ j More precisely μ is obtained as a limit of free boundary measures.
↵ k The precise picture depends on the value of k (resp. q) and can be somewhat more complicated.
↵ l Notice that for q-COL, since l is an integer, the “condensated” regime [l _c(q), l _s (q)] may be empty. This is the case for q = 4. On the contrary, q = 5 is always condensated for l _d < l < l _s.
↵ m This paradox was noticed independently by Dimitris Achlioptas (personal communication).
Abbreviations:

CSP,

constraint satisfaction problem;

rCSP,

random CSP;

k-SAT,

k-satisfiability;

q-COL,

q-coloring;

SP,

survey propagation;

BP,

belief propagation;

1RSB,

one-step replica symmetry breaking.