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.
6 pages, 4 figures, final version as accepted by International Journal of Modern Physics B
References in corpus (9)
- Supercooled Liquids for Pedestrians
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- A Landscape Analysis of Constraint Satisfaction Problems
- 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