Arnaud Durand (LACL Créteil)

On cherche parfois à savoir non seulement si un problème donné à une solution mais aussi combien il en a.

On parle dans le premier cas de problème de décision et dans le second de problème de comptage.

Un fait notable, établi par L. Valiant est que deux problèmes de décision de complexité proche peuvent avoir des problèmes de comptage associés de difficulté très différentes.

Cela sous-entend que réduire un problème de comptage (mais aussi d’énumération de solution) à un autre peut s’avérer délicat.

On rappelera, dans l’exposé, les principales notions liées au comptage et à l’énumération (formalisation d’un problème, définition des classes de complexité associées…) ainsi que les résultats les plus connus.

On présentera ensuite un certain nombre de problèmes ouverts. Puis, on introduira une nouvelle méthode de réduction qui semble convenir assez bien aux problèmes de comptage.