https://doi.org/10.1140/epjb/e2008-00052-x
Constraint optimisation and landscapes
1
PCT-ESPCI, CNRS UMR Gulliver 7083, 10 rue Vauquelin, 75005 Paris, France
2
PMMH-ESPCI, CNRS UMR 7636,
10 rue Vauquelin,
75005 Paris, France
Corresponding author: a jorge@pmmh.espci.fr
Received:
7
September
2007
Revised:
22
October
2007
Published online:
6
February
2008
We describe an effective landscape introduced in [1] for the analysis of Constraint Satisfaction problems, such as Sphere Packing, K-SAT and Graph Coloring. This geometric construction reexpresses such problems in the more familiar terms of optimisation in rugged energy landscapes. In particular, it allows one to understand the puzzling fact that unsophisticated programs are successful well beyond what was considered to be the `hard' transition, and suggests an algorithm defining a new, higher, easy-hard frontier.
PACS: 75.10.Nr – Spin-glass and other random models / 02.50.-r – Probability theory, stochastic processes, and statistics / 64.70.Pf – Glass transitions / 81.05.Rm – Porous materials; granular materials
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2008
