Random Subcubes as a Toy Model for Constraint Satisfaction Problems

2007/10/31 by Thierry Mora, Lenka Zdeborová, Lenka Zdeborova · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Constraint Satisfaction and Optimization #Optimization and Packing Problems #Theoretical and Computational Physics #cond-mat.dis-nn #cs.CC

paper · pdf · doi:10.1007/s10955-008-9543-x

published as J. Stat. Phys. 131, n. 6 (2008), 1121-1138 · 21 pages, 4 figures

arxiv created 2008/01/28 · openalex publication_date 2008/04/18 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• The Nature of Computation

Related

• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Exact Phase Transitions in Random Constraint Satisfaction Problems
• On the Freezing of Variables in Random Constraint Satisfaction Problems
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold