Random subcubes as a toy model for constraint satisfaction problems

Thierry Mora 1, 2, Lenka Zdeborova 1

Journal of Statistical Physics 131 (2008) 1121-1138

We present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random k-satisfiability and k-coloring problems, and undergoes the same phase transitions as these problems. The comparison becomes quantitative in the large-k limit. Distance properties, as well the x-satisfiability threshold, are studied. The model is also generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.

  • 1. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud
  • 2. Lewis-Sigler Institute for Integrative Genomics,
    Princeton University