ARC: projet de recherche "Méthode de compression d'entropie en combinatoire"

Il existe de nombreux problèmes algorithmiques pour lesquels aucun algorithme de résolution efficace (en temps polynomial) n'est connu. C'est par exemple le cas du problème du voyageur de commerce, qui doit parcourir le trajet le plus court entre des villes données avant de revenir à sa ville de départ : ce problème d’apparence simple ne trouve pourtant pas de solution algorithmique rapide lorsque le nombre de villes est élevé. C’est également le cas pour la satisfaisabilité des formules en logique booléenne. Pour une très grande famille de problèmes de ce type, la majorité des chercheurs suspectent qu'il n'existe simplement pas d'algorithmes efficaces. C’est la fameuse question "P?=?NP", mise au prix d'un million de dollars par le Clay Mathematics Institute.

Certains de ces problèmes deviennent cependant moins ardus en présence d'informations supplémentaires. Par exemple, si chaque variable de notre formule booléenne n'apparaît pas "trop souvent", alors nous pouvons simplement choisir au hasard les valeurs des différentes variables : la formule sera satisfaite avec une probabilité non nulle. C’est une conséquence d'un outil puissant en combinatoire, le Lemme Local de Lovasz. Cependant, cela ne nous aide pas à trouver la bonne assignation des variables.

Récemment, un réel tour de force a été réalisé par deux chercheurs, Robin Moser et Gabor Tardos : ils ont obtenu une preuve constructive du Lemme Local de Lovasz, qui donne lieu à des algorithmes efficaces pour trouver les solutions dont l'existence est garantie par le lemme. Au coeur de leur preuve se trouve une toute nouvelle technique, appelée méthode de "compression d'entropie".

Il est rapidement apparu que cette technique n'était pas limitée au Lemme Local mais pouvait être utilisée plus généralement pour obtenir de nouveaux résultats en combinatoire. Ceci a ouvert un champ d'investigation entièrement neuf et prometteur au coeur de ce projet. En explorant le potentiel et les limites des arguments de compression d'entropie, l'objectif est d'obtenir des énoncés généraux (des outils) qui peuvent être ensuite utilisés pour résoudre une large famille de problèmes combinatoires.

Porte-parole

Gwenaël Joret
Département d’Informatique
Faculté des Sciences