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 22 Novembre 2005

Pourquoi est-il si difficile de prouver qu'un problème a une borne inférieure de complexité ?

par Etienne Grandjean (GREYC)

L'un des objectifs premiers de la complexité algorithmique est d'analyser « en quoi » beaucoup de « problèmes naturels » sont intrinsèquement difficiles à résoudre. Qu'en est-il actuellement de la réalisation d'un tel objectif ? Quoiqu'on soupçonne que la classe si importante des problèmes NP-complets est formée de problèmes non polynomiaux (= la conjecture NP ≠ P) ou même exponentiels, on ne sait toujours pas prouver pour aucun problème NP-complet « naturel » une quelconque borne inférieure de complexité non triviale (= non linéaire en temps) sur un modèle de calcul de portée générale (= de type RAM).

Dans cet exposé, on donnera quelques arguments expliquant, de notre point de vue, cette difficulté étonnante à prouver des bornes inférieures de complexité : en particulier, on considérera les spécificités de quelques problèmes classiques : CIRCUIT-HAMILTONIEN, SAC-A-DOS, CLIQUE, VERTEX-COVER, etc.

L'exposé se veut très élémentaire.

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