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:
<http://arxiv.org/find/cond-mat/1/au:+Krzakala_F/0/1/0/all/0/1>Florent
Krzakala,
<http://arxiv.org/find/cond-mat/1/au:+Kurchan_J/0/1/0/all/0/1>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