Lorsqu’on pense aux liens entre physique et informatique, les développements du « hardware » et la loi de Moore viennent immédiatement à l’esprit. Depuis quelques années, un rapprochement très important mais beaucoup moins connu émerge en ce qui concerne la théorie du calcul et la complexité des algorithmes.
Les problèmes de satisfaction de contraintes, qui forment le coeur de la classe des problèmes de décision les plus difficiles en informatique, présentent bien des similitudes avec les phases vitreuses en physique, au niveau structurel -existence de contraintes antagonistes-, comme au niveau dynamique : relaxations très lentes et ralentissement des algorithmes.
L’exposé montrera comment les développements récents dans la théorie des verres structuraux permettent d’aborder et de comprendre certains éléments essentiels qui sont à l’origine de la complexité algorithmique. L’existence d’une transition vitreuse fournit une explication de la difficulté des problèmes de satisfaction de contraintes aléatoires et c’est à partir de cette analyse qu’ont été trouvés les algorithmes les plus puissants connus à ce jour pour résoudre ces problèmes.
Lien vers les colloques de l’Orme (depuis 2007).
Laboratoire de Physique Théorique et Modèles Statistiques, CNRS et Université Paris Sud