Séminaire du 8 novembre 04, Rémi Monasson et Christophe Deroulers

Le comportement critique d'algorithmes de recherche combinatoire et la classe d'universalité de la ``propagation unitaire"}

Nous nous intéressons au comportement dynamique d'algorithmes de recherche exhaustive de solutions de problèmes 3-SAT aléatoires de grande taille, dans la phase satisfaisable. Il est bien connu que, suivant l'heuristique utilisée, la plage de valeurs du rapport $\alpha:=M/N$ du nombre de clauses $M$ au nombre de variables $N$ dans laquelle la résolution est facile (en temps polynomial en $N$) est plus ou moins grande.

Plus précisément : la probabilité $P(\alpha, N)$ qu'un algorithme de recherche $A$, sans retour en arrière, donné, trouve une solution est finie si $\alpha$ est plus petit qu'un seuil $\alpha_A$ (qui dépend de l'algorithme), mais exponentiellement petite en $N$ si $\alpha$ est plus grand. Le temps de résolution par un algorithme avec retour en arrière subit donc en $\alpha_A$ une transition de polynomial à exponentiel.

Mais une analyse de différents algorithmes $A$ simples montre que, au voisinage de $\alpha_A$, la façon dont le temps de résolution diverge avec la taille $N$ du problème (``comportement critique") est universelle : pour tous les algorithmes $A$ utilisant la règle très répandue dite de propagation unitaire, $ P[(1 + \epsilon) \alpha_A, N] \sim\exp[-N^{1/6} \Phi(\epsilon N^{1/3})]$ avec la même fonction $\Phi$, que l'on sait exprimer de faŤon exacte à l'aide de la fonction d'Airy. Les exposants critiques $1/6, 1/3$ se relient à la percolation de graphes aléatoires.

Le séminaire sera composé de deux parties. Une première partie rappelera le contexte et les définitions utiles pour notre étude, et une deuxième partie plus technique présentera cette étude, exacte mais comportant des points non rigoureux, de l'heuristique de clause unitaire qui donne accès à la formule ci-dessus, avec une ``explication" de ces résultats fondée sur un phénomène de percolation.