Résumé de séminaire

Résumé :

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èmes de décision et dans le second de problèmes 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 (et réciproquement). Cela sous-entend que réduire un problème (de comptage) à un autre, tâche usuelle en complexité lorsqu'il s'agit des problèmes de décision, peut devenir délicat.

On rappelera, dans l'exposé, les principales notions liées au comptage (formalisation d'un problème, définition des classes de complexité associées) ainsi que les résultats les plus connus. Puis, on introduira une nouvelle méthode de réduction qui semble convenir assez bien aux problèmes de comptage.

Travail commun avec Miki Hermann (LORIA) et Phokion G. Kolaitis (UCSC).

Références :

Le LACL : http://www.univ-paris12.fr/lacl/

Ma home page : http://www.univ-paris12.fr/lacl/durand