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 20 Mai 2003

"Le non déterminisme rend faciles beaucoup de problèmes de graphes" ou "de la difficulté à prouver des bornes inférieures de complexité pour des problèmes naturels"

par Etienne Grandjean (GREYC)

On sait que la plupart des problèmes NP-complets combinatoires (sur les graphes, en logique, etc) sont verifiables en temps linéaire (leurs certificats sont de taille linéaire en la donnée et la vérification qu'un tel certificat est correct se fait aussi en temps linéaire déterministe), on dit qu'ils sont dans NLIN.

Dans cet exposé, on développe des outils logiques (obtenus en collaboration avec C Lautemann, F Olive et S Ranaivoson) qui permettent de montrer qu'un bon nombre de problèmes de graphes sont vérifiables en temps linéaire O(n) dans le nombre n de sommets, donc dans un sens encore plus strict (car le temps linéaire des graphes est O(n+e) où e est le nombre d'arêtes). On dit qu'ils sont de classe vertexNLIN.

Non seulement on prouve que VertexNLIN contient bon nombre de problèmes de graphes mais aussi on montre (facilement) que beaucoup d'autres problèmes de graphes ne sont pas dans cette classe et on montre que cette classe a une caractérisation logique très simple.

On conclut en argumentant sur ce pourquoi il est toujours si difficile de prouver des bornes inférieures de complexité pour les problèmes "naturels".

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