Dans les années 90 des simulations numériques ont révélées des propriétés intéressantes dans les ensembles aléatoires d’instances de problèmes de satisfaction de contraintes (satisfiabilité, coloriage de graphes notamment). Quand un paramètre définissant l’ensemble aléatoire (le nombre de clauses par variables) augmente la probabilité de trouver une formule satisfiable chute abruptement de 1 à 0 dans la limite des grandes tailles de formule. Ce phénomène de seuil a été l’objet d’actives recherches en informatique et en probabilités. Par ailleurs des outils (non-rigoureux) de physique statistique ont pu être appliqués à ces problèmes. Un certain nombre de résultats ont émergé de ces études, par exemple des conjectures quantitatives sur la valeur du seuil de satisfiabilité, et une image plus précise de la structure de l’ensemble des solutions des formules satisfiables. D’autres résultats de physique statistique ont un aspect plus algorithmique, que ce soit l’analyse d’algorithmes déjà existants ou la suggestion de nouvelles stratégies pour résoudre ces formules aléatoires. Dans ce séminaire j’essaierai de présenter, sans rentrer dans les détails techniques, le cadre général de ces études et certains de ces résultats.
- Séminaire informel de Probabilités et Statistiques