Etienne Grandjean (GREYC)

(travaux communs avec Guillaume Bagan, Arnaud Durand et Frédéric Olive).

La notion de temps linéaire dans le modèle RAM constitue un lien précis entre l’algorithmique et la théorie de la complexité. La complexité en temps linéaire est une notion robuste, naturelle et pratique.

Dans cet exposé, je présenterai d’abord quelques exemples en algorithmique et sur les requêtes en bases de données qui témoignent de l’importance du temps linéaire en pratique. Je décrirai succinctement un ensemble de problèmes de “model-checking” (est-ce qu’une structure S satisfait un certain énoncé logique F?) dont la complexité en temps est linéaire (en la taille de la structure S ): il s’agit des formules conjonctives acycliques (formules ACQ de Yannakakis) et leurs extensions, essentielles dans les bases de données.

On peut aller plus loin encore: le calcul de l’ensemble des “tuples” noté F ( S ) qui satisfont une formule fixée F (conjonctive acyclique) sans quantificateur dans une structure (= base de données) S - est calculable en temps linéaire en la taille de l’entrée (la structure S ) + la taille de la sortie (l’ensemble de tuples F ( S )). Plus finement encore, il existe, pour chaque requête F , un algorithme qui, après un précalcul linéaire (en la taille de S ), énumère les tuples du résultat à délai constant. La classe d’algorithmes d’énumération ainsi mise en évidence, appelée CONSTANT- DELAY(lin), s’avère encore une notion de complexité robuste et, en un certain sens, minimale. De plus, elle s’applique à plusieurs autres classes de requêtes, et en particulier à toutes celles définies sur les logiques et structures suivantes:

  • les formules conjonctives acycliques avec inégalités (et sans quantificateur), là encore sur toutes les structures (= bases de données quelconques),
  • la logique du premier ordre FO (First Order) sur les graphes de degré borné,
  • la logique monadique du second ordre MSO (Monadic Second Order) sur les arbres.