On dichotomy above Feder and Vardi's logic

Sur la dichotomie au-dessus de la logique de Feder et Vardi On dit d'un sous-ensemble de NP qu'il présente une dichotomie s'il contient des problèmes qui sont soit résolubles en temps polynomial (dans Ptime), soit difficiles (NP-complets). La classe des problèmes de satisfaction de contraintes (CSP) finis est un sous-ensemble bien connu de NP qui présente 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 Existentielle du second ordre (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 formule ESO.-- CSP est un sous-ensemble de la logique de Feder et Vardi, le fragment monotone, monadique et sans inégalités de SNP, lui-même un fragment syntaxique de ESO (MMSNP); et, pour chaque formule de MMSNP, il existe un problème CSP équivalent via des réductions polynomiales.Ceci implique que la logique ESO, tout comme NP, n'a pas de dichotomie, à contraster avec le fait que MMSNP a une dichotomie tout comme CSP. L'objectif principal de cette thèse est d'étudier les propriétés de dichotomie de sous-ensembles de NP qui contiennent strictement CSP ou MMSNP.Feder et Vardi ont prouvé que si nous omettons une des trois propriétés qui définissent MMSNP, à savoir être monotone, monadique ou omettre les inégalités, alors la logique résultante n'a pas de dichotomie. Comme leurs preuves restent parfois sommaires, nous revisitons ces résultats et fournissons des preuves détaillées. Le fragment guardé et monotone de SNP (GMSNP) est une extension connue de MMSNP qui est obtenue en relâchant la restriction "monadique" de MMSNP. Nous définissons de manière similaire une nouvelle logique appelée MMSNP avec des inégalités gardées, en relâchant la restriction d'être "sans inégalités". Nous prouvons qu'elle est strictement plus expressive que MMSNP et qu'elle possède également une dichotomie.Il existe une logique MMSNP₂ qui étend MMSNP de la même manière que MSO₂ étend la logique monadique du second ordre (MSO). On sait que MMSNP₂ est un fragment de GMSNP et que ces deux classes ont toutes deux une dichotomie ou n'en ont pas. Nous revisitons ce résultat et le renforçons en prouvant que, en ce qui concerne le fait d'avoir une dichotomie, sans perte de généralité, on peut considérer seulement les problèmes MMSNP₂ sur des signatures à un élément, au lieu des problèmes GMSNP sur des signatures finies arbitraires.Nous cherchons à prouver l'existence d'une dichotomie pour les MMSNP₂ en construisant en temps polynomial, pour tout problème MMSNP₂, un problème MMSNP équivalent. Nous rencontrons quelques obstacles pour construire une telle équivalence. Cependant, si nous permettons aux formules MMSNP d'être composées d'un nombre dénombrable de conjonctions négatives, nous prouvons qu'une telle équivalence existe. De plus, la formule MMSNP infinie correspondante a la propriété d'être "régulière". Cette propriété de régularité signifie que, dans un certain sens, cette formule est essentiellement finie. Il est connu que les problèmes MMSNP réguliers peuvent être exprimés par CSP sur des modèles oméga-catégoriques. De plus, il existe une caractérisation de la dichotomie algébrique pour les CSP oméga-catégoriques qui décrivent des problèmes MMSNP. Si l'on parvient à étendre cette caractérisation algébrique sur les problèmes réguliers MMSNP, alors notre résultat fournirait une dichotomie algébrique pour MMSNP₂. (...)