Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1,x2,...,xn and a list of constraints of the form "(x7,x2,...,x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. In recent years, combined logical and algebraic approaches to understand the complexity of CSPs within the complexity class P have been especially fruitful. In particular, precise algebraic conditions on Γ have been conjectured to be sufficient and necessary for the membership of CSP(Γ) in the complexity classes L and NL (under standard complexity theoretic assumptions, e.g. L different from NL). These algebraic conditions are known to be necessary, and from the algorithmic side, a promising body of evidence is fast-growing. The main tools to establish membership of CSPs in L and NL are the logic programming fragments symmetric and linear Datalog, respectively. This thesis is centered around the above algebraic conjecture for CSPs in L, and most of the technical work is devoted to establishing the membership of several large classes of CSPs in L. Among other results, we characterize all graphs for which the list homomorphism problem is in L, a well-studied and natural class of CSPs. We also extend this result to obtain a complete characterization of the complexity of the list homomorphism for graphs. We develop new tool (dualities for symmetric Datalog) to show membership of CSPs in L, prove an L − NL dichotomy for the list homomorphism problem for oriented paths, provide results about the structure and polymorphisms of Maltsev digraphs, and also contribute to the conjecture of Dalmau that every CSP in NL is in fact in linear Datalog. / Les problèmes de satisfaction de contraintes (ou CSP) forment un cadre particulièrement riche permettant de formaliser de façon uniforme un grand nombre de problèmes algorithmiques tirés de l'optimisation combinatoire, de l'intelligence artificielle et de la théorie des bases de données. À chaque domaine D et chaque langage de contraintes Γ (i.e. un ensemble de relations sur D), on associe le problème CSP(Γ) suivant. Une instance du problème est constituée d'une liste de variables x1,...,xn et d'une liste de contraintes de la forme (x7,x2,...,x5) ∈ R, où R ∈ Γ. On cherche à déterminer si des valeurs de D peuvent être assignées aux variables de telle sorte que les contraintes soient toutes satisfaites simultanément. La complexité algorithmique de CSP(Γ) est entièrement fonction de la structure du langage de contraintes Γ et on cherche alors à identifier des classes de contraintes pour lesquelles CSP(Γ) appartient à une classe de complexité spécifique. Récemment, la combinaison des approches logique et algébrique a porté fruits dans la compréhension de la complexité des CSP à l'intérieur de la classe P. En particulier, on a conjecturé des conditions algébriques nécessaires et suffisantes précises pour l'appartenance de CSP(Γ) dans les classes L et NL (sous les hypothèses habituelles en théorie de la complexité, e.g. L est différent de NL). Ces conditions algébriques sont sues être nécessaires, et d'un point de vue algorithmique, les indications en faveur du résultat s'accumulent rapidement. Les outils principaux pour établir l'appartenance d'un CSP à L ou NL sont respectivement les fragments "symmetric Datalog" et "linear Datalog" en programmation logique. Notre thèse est centrée sur la conjecture algébrique ci-haut mentionnée pour les CSP dans L, et la majeure partie du travail technique est dédiée à montrer l'appartenance de plusieurs grandes familles de CSP dans L. Entre autres résultats, nous caractérisons tous les graphes pour lesquels le problème de "list homomorphism" est dans L, une famille naturelle et bien étudiée de CSP. Nous étendons aussi ce résultat pour obtenir une caractérisation complète de la question pour les graphes. Nous développons de nouveaux outils (les dualités pour "symmetric Datalog") pour montrer l'appartenance de CSP dans L, nous prouvons une dichotomie L-NL pour les problèmes de "list homomorphism" pour les chemins orientés, nous donnons des résultats sur la structure et les polymorphismes des digraphes de Maltsev, et nous contribuons à la conjecture de Dalmau à l'effet que chaque CSP dans NL est en fait dans "linear Datalog".
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.114132 |
| Date | January 2013 |
| Creators | Egri, László |
| Contributors | Denis Therien (Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0026 seconds