Onset of hardness in random glassy problems
Abstract Book of the XXIII IUPAP International Conference on Statistical Physics, Genova, Italy, (9-13 July 2007)Аннотация
Over the last few years, a number of breakthroughs have been made in the spin glass-like analysis of random constraint satisfaction problems such as K-SAT or coloring. A simple question remains however unanswered: When are such problem hard to solve with simple local solvers ? . Indeed, very simple random walk-like solvers have been remarkably and easily able to beat the heuristic bounds computed by the physicists !
The new and more precise characterization of the phase space of solutions that has been developed this year allows to solve this apparent paradox and to give a plausible bound to the efficiency of local solvers. This happens BEYOND the usual mode-coupling/dynamics transition, when a kind of freezing transition occurs within the states. The connection of this phenomena with glass-like models, the jamming transition and the glass phenomenology will also be discussed.