Florent Madelaine (LACL, Univ. Paris-Est Créteil)

Dans cet exposé, je reviens sur la complexité d’une extension quantifiée des problèmes de satisfaction de contraintes (QCSP) qui est un analogue de QBF. En toute généralité, le problème est Pspace-complet. Comme dans le cadre du théorème de dichotomie de Bulatov-Zhuk pour les problèmes de satisfaction de contraintes, il s’agit d’étudier les restrictions du problème général en forçant les contraintes à appartenir à un langage; et, la complexité d’un langage dépend d’une algèbre associée.

On esquissera d’abord un premier résultat de “facilité” qui stipule que si la séquence des puissances de l’algèbre associée à un langage a des petits générateurs (polynomially generated powers en jargon) alors le problème est dans NP.

Dans un second temps on évoquera un résultat de “difficulté” qui stipule que si au contraire cette séquence a de grands générateurs (exponentially generated powers en jargon) alors une paramétrisation différente du QCSP est co-NP-difficile. On discutera en détail de cette paramétrisation qui consiste à étudier des langages de contraintes infinis (et donc à devoir expliciter leur représentation).

Ceci est le fruit d’une collaboration avec Catarina Carvalho, Barnaby Martin et Dmitriy Zhuk.