Johann Brault-Baron (GREYC, Caen)

À quoi reconnaît-on une question difficile ? C’est la question que l’on se pose dans le cadre des problèmes exprimés dans la logique existentielle du premier ordre : on cherche à mettre en rapport la forme d’un énoncé logique (sa formulation) et la complexité du problème associé, que l’on appelle aussi requête.

Un premier résultat a été établi (partiellement) par G. Bagan qui énonce que, en ce qui concerne le fragment des requêtes conjonctives, la classe bien connue des requêtes dites acycliques caractérise le temps linéaire (pour ce fragment).

On fournit un résultat similaire (mais dissymétrique) pour la classe duale de la classe des requêtes conjonctives.

Enfin, on unifie ces deux résultats dans une caractérisation qui ouvre la possibilité d’une caractérisation des requêtes du premier ordre existentiel décidables en temps linéaire.