On dichotomy above Feder and Vardi's logic

Autor: Barsukov, Alexey
Přispěvatelé: Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA), Université Clermont Auvergne, Mamadou Moustapha Kanté, Mamadou Moustapha Kanté, Florent Madelaine
Jazyk: angličtina
Rok vydání: 2022
Předmět:
Zdroj: Computational Complexity [cs.CC]. Université Clermont Auvergne, 2022. English. ⟨NNT : 2022UCFAC092⟩
Computational Complexity [cs.CC]. Université Clermont Auvergne (UCA), 2022. English. ⟨NNT : ⟩
Popis: A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-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 P-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.Feder and Vardi proved that if we omit one of the three properties that define MMSNP, namely being monotone, monadic or omitting inequalities, then the resulting logic does not have a dichotomy. As their proofs remain sketchy at times, we revisit these results and provide detailed proofs. Guarded Monotone Strict NP (GMSNP) is a known extension of MMSNP that is obtained by relaxing the "monadic" restriction of MMSNP. We define similarly a new logic that is called MMSNP with Guarded inequalities, relaxing the restriction of being "without inequalities". We prove that it is strictly more expressive than MMSNP and that it also has a dichotomy.There is a logic MMSNP₂ that extends MMSNP in the same way as MSO₂ extends Monadic Second-Order (MSO) logic. It is known that MMSNP₂ is a fragment of GMSNP and that these two classes either both have a dichotomy or both have not. We revisit this result and strengthen it by proving that, with respect to having a dichotomy, without loss of generality, one can consider only MMSNP₂ problems over one-element signatures, instead of GMSNP problems over arbitrary finite signatures.We seek to prove the existence of a dichotomy for MMSNP₂ by finding, for every MMSNP₂ problem, a P-time equivalent MMSNP problem. We face some obstacles to build such an equivalence. However, if we allow MMSNP sentences to consist of countably many negated conjuncts, then we prove that such an equivalence exists. Moreover, the corresponding infinite MMSNP sentence has a property of being "regular". This regular property means that, in some sense, this sentence is still finite. It is known that regular MMSNP problems can be expressed by CSP on omega-categorical templates. Also, there is an algebraic dichotomy characterisation for omega-categorical CSPs that describe MMSNP problems. If one manages to extend this algebraic characterisation onto regular MMSNP, then our result would provide an algebraic dichotomy for MMSNP₂.Another potential way to prove the existence of a dichotomy for MMSNP₂ is to mimic the proof of Feder and Vardi for MMSNP. That is, by finding a P-time equivalent CSP problem. The most difficult part there is to reduce a given input structure to a structure of sufficiently large girth. For MMSNP and CSP, it is done using expanders, i.e., structures, where the distribution of tuples is close to a uniform distribution. We study this approach with respect to MMSNP₂ and point out the main obstacles.We also consider an extension of CSP: the Matrix Partition (MP) problems class. We study it from several perspectives. It is well-known that CSP over an arbitrary finite signature has a dichotomy if and only if CSP on directed graphs has a dichotomy. Motivated by this result, we consider MP problems over arbitrary finite signatures and show that they have a dichotomy if and only if MP problems over one-element signatures have a dichotomy, similarly to our result for MMSNP₂. Another perspective is to characterise MP problems with respect to being definable in First-Order (FO) logic. For CSP, a problem is FO-definable if and only if it has a finitary duality, i.e., a finite family of digraphs such that an input digraph is accepted by the CSP if and only if no digraph from the family is homomorphically mapped to the input one. There have already been some attempts to classify Matrix Partition problems in terms of having finitely many minimal obstructions, i.e., an input graph is accepted by the MP problem if and only if it does not contain an induced subgraph from a given finite family. We manage to show that, for MP problems, these two notions are the same. The third perspective is to find a logic that would be related to MP in a similar way as MMSNP is related to CSP. We introduce, as a potential candidate, a logic obtained from MMSNP by relaxing the "monotone" restriction, and show that it contains MP. However, it is not known how to show the equivalence. At last, we study the notion of "polymorphism" for MP problems. We do it in order to consider the algebraic dichotomy characterisation for finite CSP and see if there is some potential to consider polymorphisms for MP problems. In the case of CSP, a structure has a non-trivial polymorphism if and only if the corresponding CSP is P-time solvable. We manage to provide an MP problem that has only trivial polymorphisms and that is P-time solvable. This means that, for MP problems, the existence of an algebraic characterisation is unlikely.In an independent chapter, we investigate the Maximum Cut (maxcut) problem. Although being NP-complete in general, its complexity becomes unknown if we consider only unit interval graphs in the input. Knowing that maxcut is NP-complete on interval graphs, we approach as close as possible to unit interval graphs by proving that it remains NP-complete even if we are allowed to operate with intervals of only two different lengths.; 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₂.Une autre façon potentielle de prouver l'existence d'une dichotomie pour MMSNP₂ est d'imiter la preuve de Feder et Vardi pour MMSNP. C'est-à-dire, en trouvant un problème CSP équivalent à réduction polynomial près. La partie la plus difficile est de réduire une structure d'entrée donnée à une structure de maille suffisamment grande. Pour MMSNP et CSP, cela est fait en utilisant des expanseurs, c'est-à-dire des structures où la distribution des tuples est proche d'une distribution uniforme. Nous étudions cette approche dans le cas de MMSNP₂ et soulignons les principaux obstacles.Nous considérons également une extension de CSP : la classe des problèmes de partition matricielle (MP). Nous l'étudions sous plusieurs angles. Il est bien connu que CSP sur une signature finie arbitraire a une dichotomie si et seulement si CSP sur des graphes dirigés a une dichotomie. Motivés par ce résultat, nous considérons les problèmes MP sur des signatures finies arbitraires et montrons qu'ils ont une dichotomie si et seulement si les problèmes MP sur des signatures à un élément ont une dichotomie, de manière similaire à notre résultat pour MMSNP₂. Une autre perspective est de caractériser les problèmes MP par rapport à leur définissabilité en logique du premier ordre (FO). Pour le CSP, un problème est définissable en logique du premier ordre si, et seulement si, il a une dualité finitaire, c'est-à-dire une famille finie de digraphes telle qu'un digraphe d'entrée est accepté par le CSP si, et seulement si, aucun digraphe de la famille n'est homomorphe à celui d'entrée. Il y a déjà eu quelques tentatives pour classer les problèmes de partition matricielle en fonction de l'existence d'un nombre fini d'obstructions minimales, c'est-à-dire qu'un graphe d'entrée est accepté par le problème MP si et seulement s'il ne contient pas de sous-graphe induit d'une famille finie donnée. Nous parvenons à montrer que, pour les problèmes MP, ces deux notions sont les mêmes. La troisième perspective est de trouver une logique qui serait liée à MP d'une manière similaire à celle de MMSNP par rapport à CSP. Nous introduisons, comme candidat potentiel, une logique obtenue à partir de MMSNP en relâchant la restriction "monotone", et montrons qu'elle contient MP. Cependant, nous ne savons pas comment montrer l'équivalence. Enfin, nous étudions la notion de "polymorphisme" pour les problèmes MP. Nous le faisons afin de considérer la caractérisation de la dichotomie algébrique pour les CSP finis et de voir s'il existe un potentiel pour considérer les polymorphismes pour les problèmes MP. Dans le cas des CSP, une structure a un polymorphisme non-trivial si, et seulement si, le CSP correspondant peut être résolu en temps polynomial. Nous parvenons à fournir un problème MP qui n'a que des polymorphismes triviaux et qui peut être résolu en temps polynomial. Cela signifie que, pour les problèmes MP, l'existence d'une caractérisation algébrique est peu probable.Dans un chapitre indépendant, nous étudions le problème du Maximum Cut (maxcut). Bien qu'il soit NP-complet en général, sa complexité devient inconnue si nous ne considérons que les graphes d'intervalles unitaires en entrée. Sachant que maxcut est NP-complet sur les graphes d'intervalles, nous nous approchons le plus possible des graphes d'intervalles unitaires en prouvant qu'il reste NP-complet même si nous sommes autorisés à opérer avec des intervalles de seulement deux longueurs différentes.
Databáze: OpenAIRE
Externí odkaz: