Il y a environ dix ans, des informaticiens découvraient les phénomènes de seuil. Lorsque l’on modifie très peu les données d’entrée de problèmes d’optimisation (satisfaction de contraintes, coloriage de graphe, …), les temps de résolution peuvent changer brutalement. Ce comportement surprenant est similaire à ce qui est observé au voisinage des transitions de phase en physique, et peut donc être étudié à l’aide de méthodes de la physique statistique. Je décrirai quelques travaux récents dans le domaine et discuterai l’intérêt et les limitations de ces avancées.

Laboratoire de Physique Théorique de l’ENS 24, rue Lhomond, F-75005 Paris