“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”

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