Landscape analysis of constraint satisfaction problems

2007/02/28 by Florent Krzakala, Florent Krząkała, Jorge Kurchan · 7 citations
Agricultural and Biological Sciences · Computer Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Benchmark (surveying) #Cluster analysis #Combinatorics #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Context (archaeology) #Data Visualization and Analytics #Geography #Geometry #Graph #Graph coloring #Mathematical optimization #Mathematics #Packing problems #Point (geometry) #Sensory Analysis and Statistical Methods #Simple (philosophy) #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC #nlin.CD

paper · pdf · doi:10.1103/physreve.76.021122

published as Phys. Rev. E 76, 021122 (2007) · 17 pages, 69 citations, 12 figures

arxiv created 2007/06/18 · openalex publication_date 2007/08/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A benchmark algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the clustering and in some cases even the thermodynamic transitions. This point has a simple geometric meaning and can be in principle determined with standard statistical mechanical methods, thus pushing the analytic bound up to which problems are guaranteed to be easy. We illustrate this for the graph 3- and 4-coloring problem. For packing problems the present discussion allows to better characterize the J-point, proposed as a systematic definition of random close packing, and to place it in the context of other theories of glasses.

Citations

• Threshold values, stability analysis, and high-qasymptotics for the coloring problem on random graphs
• Cooling-schedule dependence of the dynamics of mean-field glasses
• Jamming at zero temperature and zero applied stress: The epitome of disorder
• On the rigidity of amorphous solids
• Gibbs states and the set of solutions of random constraint satisfaction problems

Cited by

• Memory of jamming–multiscale models for soft and granular matter
• Critical scaling and heterogeneous superdiffusion across the jamming/rigidity transition of a granular glass
• Locked Constraint Satisfaction Problems
• A first-order phase transition defines the random close packing of hard spheres
• Etude expérimentale de l’émission de neutrons retardés issus de la photofission des actinides
• Free volume distribution of nearly jammed hard sphere packings
• Combined local search strategy for learning in networks of binary synapses