A subset of NP is said to have a dichotomy if it contains problem that are either solvable in polynomial time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity class NP does not have a dichotomy unless P = NP. For both of these classes there exist logics that are associated with them.
- NP is captured by Existential Second-Order (ESO) logic by Fagin's theorem, i.e., a problem is in NP if and only if it is expressible by an ESO sentence.
- CSP is a subset of Feder and Vardi's logic, Monotone Monadic Strict NP without inequalities (MMSNP), and for every MMSNP sentence there exists a polynomial time equivalent CSP problem.
This implies that ESO does not have a dichotomy as well as NP, and that MMSNP has a dichotomy as well as CSP. The main objective of this thesis is to study subsets of NP that strictly contain CSP or MMSNP with respect to the dichotomy existence.

Committee:
Nadia Creignou - Aix-Marseille University - Examiner
Víctor Dalmau - Pompeu Fabra University - Referee
Arnaud Durand - Paris Diderot University - Referee
Mamadou Kanté - Clermont Auvergne University - Supervisor
Florent Madelaine - Paris-East Créteil University - Co-supervisor
Lhouari Nourine - Clermont Auvergne University - Examiner
Aline Parreau - CNRS, Claude Bernard University Lyon 1 - Examiner
Yann Strozecki - University of Versailles Saint-Quentin-en-Yvelines - Refere.

Link to visioconference: https://u-pec-fr.zoom.us/j/96110557959?pwd=cDA2WXN0dFZqRXhvUy9iamNUYWtHZz09