Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2007-02-23
Phys. Rev. E 76, 021122 (2007)
Physics
Condensed Matter
Statistical Mechanics
17 pages, 69 citations, 12 figures
Scientific paper
10.1103/PhysRevE.76.021122
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.
Krzakala Florent
Kurchan Jorge
No associations
LandOfFree
A Landscape Analysis of Constraint Satisfaction Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Landscape Analysis of Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Landscape Analysis of Constraint Satisfaction Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-691434