Landscape of Solutions in Constraint Satisfaction Problems
Open Access
- 10 November 2005
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 95 (20) , 200202
- https://doi.org/10.1103/physrevlett.95.200202
Abstract
We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Source coding by efficient selection of ground-state clustersPhysical Review E, 2005
- Rigorous location of phase transitions in hard optimization problemsNature, 2005
- Clustering of Solutions in the Random Satisfiability ProblemPhysical Review Letters, 2005
- The Cavity Method for the Rigidity TransitionJournal of Statistical Physics, 2005
- The Cavity Method at Zero TemperatureJournal of Statistical Physics, 2003
- Random-satisfiability problem: From an analytic solution to an efficient algorithmPhysical Review E, 2002
- Analytic and Algorithmic Solution of Random Satisfiability ProblemsScience, 2002
- A variational description of the ground state structure in random satisfiability problemsZeitschrift für Physik B Condensed Matter, 2000
- Determining computational complexity from characteristic ‘phase transitions’Nature, 1999
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979