Random subcubes as a toy model for constraint satisfaction problems

Thierry Mora ^1, 2, Lenka Zdeborova ¹

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