Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 30 Octobre 2001

Comptage, énumération et réduction

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr