Florent Madelaine (GREYC, Caen)

Le problème de satisfaction de contraintes quantifiées (QCSP) permet de modéliser le fait que certaines variables ne sont pas contrôlables mais dépendent de l’environnement. Cette extension du modèle classique a un coût non négligeable : on obtient alors un problème PSpace-complet plutôt que seulement NP-complet pour le modèle classique. Une conséquence concrète de ce saut de complexité est que contrairement, aux solveurs de contraintes (solveurs CSP) avec lesquels on peut modéliser et traiter de très larges instances de problèmes “du monde réel”, les solveurs QCSP restent des prototypes académiques peu ou pas utilisés ne pouvant pas vraiment traiter plus que des problèmes jouets.

Dans cet exposé, je vais expliquer le genre de restrictions qu’on peut espérer appliquer à un QCSP pour limiter sa complexité; en argumentant que dans ce contexte généralisé, être un QCSP facile correspond à pouvoir résoudre une instance en faisant un nombre faible d’appels à un solveur CSP. Finalement, je vais conclure en évoquant des résultats récents concernant la différence entre QCSP faciles et difficiles (travail commun avec Barnaby Martin et Catarina Carvalho accepté à LICS 2015).

Cet exposé ne se veut pas technique et est destiné à un public aussi large que possible. Lors d’une séance future du groupe de travail organisé par Jean Creusefond, je vais soulever le capot pour esquisser ces savoureux détails techniques.