Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

Florent Krzakala 1, Lenka Zdeborová 2

Journal of Physics: Conference Series 95 (2008) 012012

We review the understanding of the random constraint satisfaction problems, focusing on the q-coloring of large random graphs, that has been achieved using the cavity method of the physicists. We also discuss the properties of the phase diagram in temperature, the connections with the glass transition phenomenology in physics, and the related algorithmic issues.

  • 1. Laboratoire de Physico-Chimie Théorique (LPCT),
    CNRS : UMR7083 – ESPCI ParisTech
  • 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud