https://doi.org/10.1140/epjb/e2008-00324-5
Solution clustering in random satisfiability
Department of Computer Science, University of California Santa Cruz, 1156 High Street MS:SOE3, 95064 Santa Cruz, USA
Corresponding author: a optas@cs.ucsc.edu
Received:
31
August
2007
Revised:
22
May
2008
Published online:
15
August
2008
For a large number of random constraint satisfaction problems, such as random k-SAT and random graph and hypergraph
coloring, we have very good estimates of the largest constraint density for which solutions exist. All known polynomial-time
algorithms for these problems, though, fail to find solutions at much lower densities. To understand the origin of this gap we
study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we show that
in random k-SAT for , much before solutions disappear, they organize into an exponential number of clusters, each of
which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e.,
take only one value.
PACS: 02.50.-r – Probability theory, stochastic processes, and statistics / 75.10.Nr – Spin-glass and other random models
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2008