Enumération dans les graphes et les hypergraphes: algorithmes et complexité

La question "P = NP?" est le problème le plus important en informatique fondamentale. Partant du postulat que les classes de complexité P et NP sont différentes, il y a des problèmes que l'on ne peut résoudre efficacement à l'aide de l'ordinateur. C'est pourquoi il est important de trouver de nouvelles approches pour les aborder, autres que les algorithmes polynomiaux classiques.

Alors que l'optimisation est omniprésente en informatique et que l'on y trouve énormément de travaux sur l'algorithmique et la complexité des problèmes d'optimisation, peu d'attention a été accordée à l'énumération. Un algorithme pour la version "énumération" d'un problème fournira immédiatement une solution optimale pour la version "optimisation" du même problème. Ceci suggère que l'énumération serait nettement plus difficile que l'optimisation, d'où, entre autres, le moindre intérêt des chercheurs pour l'énumération. Cependant, des résultats récents sur la complexité des problèmes difficiles montrent que les relations entre la difficulté de l'énumération et celle de l'optimisation sont plus subtiles et méritent une étude approfondie.