Florent Madelaine (LAIC, Clermont-Ferrand)

On s’intéresse à une généralisation des problèmes de contraintes quantifiés. Chaque problème est paramétré par une structure relationnelle fixée B : le domaine de B correspondant aux valeurs que peuvent prendre une variable et les relations de B aux différentes contraintes. Une instance du problème est une formule du premier ordre n’utilisant que les connecteurs ‘et’ et ‘ou’ (pas de négation) et dont chaque variable est quantifiée existentiellement ou universellement. Notons que les problèmes de contraintes quantifiés classiques n’utilisent pas la disjonction.

Du point de vue de la modélisation, on peut considérer que les variables existentielles sont sous notre contrôle et que nous pouvons choisir leurs valeurs afin de satisfaire les contraintes, alors que les variables universelles sont hors de notre contrôle, dépendantes de l’environnement ou contrôlées par un adversaire malicieux.

Pour une structure B bien choisie, on peut facilement coder des variantes de QSAT dans ce formalisme, obtenant ainsi des problèmes Pspace-complets. Pour d’autres structures B , la complexité est moindre: Co-NP-complet, NP- complet ou encore dans Logspace. De manière générale, on cherche à caractériser la complexité de chaque problème en fonction de B.

Dans cet exposé, on verra que les hyper-endomorphismes surjectifs semblent être le bon objet algébrique permettant d’obtenir une caractérisation de la complexité des problèmes de contraintes quantifiées. On présentera la machinerie algébrique nécessaire puis on esquissera les grandes lignes de résultats de polychotomies obtenus lorsque le domaine de B est de petite taille.