Date : Dec. 13, 2022, 8:30 a.m. - Alexey BARSUKOV - Salle du conseil
On dichotomy above Feder and Vardi's logic
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.
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