A Landscape Analysis of Constraint Satisfaction Problems

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 three and four-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.

17 pages, 69 citations, 12 figures

References in corpus (2)

• Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Cited by in corpus (8)

• Critical scaling and heterogeneous superdiffusion across the jamming/rigidity transition of a granular glass
• Locked constraint satisfaction problems
• Random subcubes as a toy model for constraint satisfaction problems
• A Lattice Model for Colloidal Gels and Glasses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Constraint optimization and landscapes
• Introduction to Phase Transitions in Random Optimization Problems