HdR Florent Madelaine le 4 décembre à Clermont-Ferrand

Pour plus de détails concernant la journée de soutenance, le jury et accéder au mémoire, voir ici.

Résumé

Mon travail s’articule autour des problèmes de satisfaction de contraintes (CSP) et de leurs extensions comme les problèmes de contraintes quantifiés (QCSP), la question essentielle étant de comprendre leur complexité. Ceux- ci peuvent être vus comme des problèmes de model-checking pour certains fragments de la logique du premier ordre. Dans le cas des CSP, Feder et Vardi ont proposé la conjecture de la dichotomie, à savoir que chaque problème CSP est soit facile (dans P) soit difficile (NP-complet). Dans le cas des QCSP, il n’existe pas encore de conjecture mature, mais une trichotomie entre P, NP-complet et Pspace-complet est envisageable.

Mon manuscrit comporte deux parties: la première sur la complexité du model checking pour les fragments syntaxiques de la logique du premier ordre; et, la seconde sur des questions autour de la logique MMSNP de Feder et Vardi, qui est intimement liée à la classe des CSP.