On dit qu'un sous-ensemble de NP a une dichotomie s'il contient des problèmes qui sont soit solubles en temps polynomial, soit NP-complets. La classe des problèmes finis de satisfaction de contraintes (CSP) est un sous-ensemble bien connu de NP qui suit une telle dichotomie. La classe de complexité NP n'a pas de dichotomie à moins que P = NP. Pour ces deux classes, il existe des logiques qui leur sont associées.
- NP est capturé par la logique Existential Second-Order (ESO) par le théorème de Fagin, c'est-à-dire qu'un problème est dans NP si et seulement s'il est exprimable par une phrase ESO.
- CSP est un sous-ensemble de la logique de Feder et Vardi, Monotone Monadic Strict NP sans inégalités (MMSNP), et pour chaque phrase MMSNP il existe un problème CSP équivalent en temps polynomial.
Ceci implique que ESO n'a pas de dichotomie ainsi que NP, et que MMSNP a une dichotomie ainsi que CSP. L'objectif principal de cette thèse est d'étudier les sous-ensembles de NP qui contiennent strictement CSP ou MMSNP en ce qui concerne l'existence de la dichotomie.

Jury :
Nadia Creignou - Aix-Marseille Université - Examinatrice
Víctor Dalmau - Université Pompeu Fabra - Rapporteur
Arnaud Durand - Université Paris Diderot - Rapporteur
Mamadou Kanté - Université Clermont Auvergne - Directeur
Florent Madelaine - Université Paris-Est Créteil - Encadrant
Lhouari Nourine - Université Clermont Auvergne - Examinateur
Aline Parreau - CNRS, Université Claude Bernard Lyon 1 - Examinatrice
Yann Strozecki - Université de Versailles Saint-Quentin-en-Yvelines - Rapporteur.

Lien vers la visioconférence : https://u-pec-fr.zoom.us/j/96110557959?pwd=cDA2WXN0dFZqRXhvUy9iamNUYWtHZz09