Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems

Abstract

An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space (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 for the first time 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 beat also this threshold.

6 pages, 6 figures, slightly revised version

References in corpus (2)

• Clustering of solutions in the random satisfiability problem
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Cited by in corpus (35)

• Critical phenomena in complex networks
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Simple Glass Models and their Quantum Annealing
• On the freezing of variables in random constraint satisfaction problems
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Reconstruction of Random Colourings
• Statistical Mechanics of Steiner trees
• Potts Glass on Random Graphs
• Random subcubes as a toy model for constraint satisfaction problems
• A Lattice Model for Colloidal Gels and Glasses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• A rigorous analysis of the cavity equations for the minimum spanning tree
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Reconstruction of symmetric Potts Models
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Ground-State Entropy of the Random Vertex-Cover Problem
• Entropic Effects in the Very Low Temperature Regime of Diluted Ising Spin Glasses with Discrete Couplings
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Complex Replica Zeros of $\pm J$ Ising Spin Glass at Zero Temperature
• Random Constraint Satisfaction Problems
• Constraint optimization and landscapes
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Clustering of solutions in hard satisfiability problems
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Introduction to Phase Transitions in Random Optimization Problems
• Statistical Mechanics of the Quantum K-Satisfiability problem
• A simple one dimensional glassy Kac model