Landscape of solutions in constraint satisfaction problems

Marc Mezard 1, Matteo Palassini 1, 2, Olivier Rivoire 1

Physical Review Letters 95 (2005) 200202

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.

  • 1. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud
  • 2. Departament de Física Fonamental,
    Universitat de Barcelona