Phase transitions: from physics to computer science
Constraint satisfaction problems (graph colouring, routing, etc...) appear in many applications of computer science. They are also at the core of complexity theory: The satisfiability problem has been the first one shown to be “NP-complete". This does not leave much hope of solving it in a number of operations growing like a power of the number of variables. The formulation of this problem is very simple: in physical terms, one just needs to find whether there exists a configuration of an Ising spin system which satisfies some given constraints. Recent work has shown that the difficulty of this problem is linked to the existence of a phase transition at some value of the number of constraints per variable. Taking satisfiability as a guideline, this talk presents an introduction to the statistical physics of optimization problems. It focuses on the existence of glass phases, and the dramatic slowing down of algorithms that it induces. The theoretical understanding of these phases helps to develop new classes of efficient algorithms.