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.