Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems
arXiv:0911.4328 · doi:10.1142/S0217979210056013
Abstract
Random constraint satisfaction problems are interesting model systems for spin-glasses and glassy dynamics studies. As the constraint density of such a system reaches certain threshold value, its solution space may split into extremely many clusters. In this paper we argue that this ergodicity-breaking transition is preceded by a homogeneity-breaking transition. For random K-SAT and K-XORSAT, we show that many solution communities start to form in the solution space as the constraint density reaches a critical value alpha_cm, with each community containing a set of solutions that are more similar with each other than with the outsider solutions. At alpha_cm the solution space is in a critical state. The connection of these results to the onset of dynamical heterogeneity in lattice glass models is discussed.
arXiv comment6 pages, 4 figures, final version as accepted by International Journal of Modern Physics B
References in corpus (16)
- The Bethe lattice spin glass revisited
- Supercooled Liquids for Pedestrians
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Lattice Glass Models
- The Entropy of the K-Satisfiability Problem
- A Landscape Analysis of Constraint Satisfaction Problems
- Reconstruction on trees and spin glass transition
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Simplest random K-satisfiability problem
- On the dynamics of the glass transition on Bethe lattices
- Generalization of the cavity method for adiabatic evolution of Gibbs states
- Circumspect descent prevails in solving random constraint satisfaction problems
- Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
- Dynamical Heterogeneity in Lattice Glass Models
- Communities of solutions in single solution clusters of a random K-Satisfiability formula
- Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula