CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS
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 work 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 αcm, with each community containing a set of solutions that are more similar with each other than with the outsider solutions. At α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.
This paper was presented at the 5th Singapore-China Joint Symposium on Research Frontiers in Physics which took place from 22–24 July 2009, in the premises of University Hall Auditorium, National University of Singapore.
| You currently do not have access to the full text article. |
|---|
