Florent Madelaine (université de Durham)

Les problèmes de satisfaction de contraintes (CSP) forment une large classe de problèmes dans NP, qui contient des problèmes NP-complets tels SAT ou 3-Col. Fagin a montré que NP correspond exactement aux problèmes qui peuvent s’exprimer à l’aide de formules de la logique existentielle du second ordre (ESO). Feder et Vardi ont mis en évidence une restriction de ESO qui bien que trop expressive est “proche” de CSP: la logique MMSNP.

Dans des travaux précédents j’ai déterminé exactement la frontière entre CSP et MMSNP. En fait, plutôt que de travailler dans le contexte logique, j’ai donné une “traduction” combinatoire de MMSNP, à savoir la classe des problèmes de motifs (coloriés) interdits. Un exemple typique de problème de motif interdit qui n’est pas dans CSP est le problème de graphes “pas de triangle Monochromatique”. Ce problème prend comme instance un graphe et accepte ce graphe si et seulement si il existe une partition de ces sommets en deux parties (deux “couleurs”) telle que chaque partie soit sans triangle.

Plus récemment, je me suis penché sur le problème inverse: sous quelles restrictions (de la classe des instances), la logique MMSNP capture exactement CSP (avec les mêmes restrictions sur la classe des instances). Je donne un exemple d’une telle restriction. lorsque toute instance est connexe et de degré borné. Par exemple, le problème “pas de triangle Monochromatique” est en fait un CSP, si on restreint les instances à être à la fois connexes et de degré borné.

Dans une première partie de l’exposé, je vais résumer quelques résultats liés à CSP et MMSNP que je vais illustrer par plusieurs exemples. Dans une seconde partie de l’exposé, je vais essayer de donner l’intuition de la preuve du résultat suivant. les problèmes de motifs interdits sont en fait des problèmes de satisfaction de contraintes lorsque les instances sont à la fois connexes et de degré borné. Finalement, je vais conclure par quelques questions.