Dear everybody,
The paper I mentioned today about spin glass
people trying to calculate energy landscapes of random instances of
NP-complete optimization problems and trying to find average-case
classical polynomial time algorithms for certain classes thereof is the
following. I think it's especially valuable as a guide to the
literature (though note it's more on the question of "when is
annealing efficient" than message-passing /
belief-propagation).
A Landscape Analysis of Constraint Satisfaction
Problems
http://arxiv.org/abs/cond-mat/0702546
Authors:
Florent Krzakala,
Jorge Kurchan
Comments: 16 pages, 60 citations, 12 figures
Subj-class: Statistical Mechanics; Disordered Systems and Neural
Networks; Computational Complexity
- 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.
[NB: The tantalizing "to be published" reference in the
above paper claiming that "quantum annealing" can't efficiently
generate the ground states of a famous type of mean field spin glass is
[25] L.F. Cugliandolo, D. Grempel, G. Lozano, and H. Lozza... these 4
people are physicists who've done seminal work in the thermal dynamics of
classical and quantum spin glasses.]
Regards,
Bill