- Authors
- Antoine Mottet
- title
- Dichotomies in Constraint Satisfaction: Canonical Functions and Numeric CSPs
- Please use the following URL when quoting:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-315310
- Date of submission
- 31.05.2018
- Date of defense
- 14.08.2018
- Abstract (DE)
- Constraint satisfaction problems (CSPs) form a large class of decision problems that con- tains numerous classical problems like the satisﬁability problem for propositional formulas and the graph colourability problem. Feder and Vardi [52] gave the following logical for- malization of the class of CSPs: every ﬁnite relational structure A, the template, gives rise to the decision problem of determining whether there exists a homomorphism from a ﬁnite input structure B to A. In their seminal paper, Feder and Vardi recognised that CSPs had a particular status in the landscape of computational complexity: despite the generality of these problems, it seemed impossible to construct NP-intermediate problems `a la Ladner [72] within this class. The authors thus conjectured that the class of CSPs satisﬁes a complexity dichotomy , i.e., that every CSP is solvable in polynomial time or is NP-complete. The Feder-Vardi dichotomy conjecture was the motivation of an intensive line of research over the last two decades. Some of the landmarks of this research are the conﬁrmation of the conjecture for special classes of templates, e.g., for the class of undi- rected graphs [55], for the class of smooth digraphs [5], and for templates with at most three elements [43, 84]. Finally, after being open for 25 years, Bulatov [44] and Zhuk [87] independently proved that the conjecture of Feder and Vardi indeed holds. The success of the research program on the Feder-Vardi conjecture is based on the con- nection between constraint satisfaction problems and universal algebra. In their seminal paper, Feder and Vardi described polynomial-time algorithms for CSPs whose template satisﬁes some closure properties. These closure properties are properties of the polymor- phism clone of the template and similar properties were later used to provide tractability or hardness criteria [61, 62]. Shortly thereafter, Bulatov, Jeavons, and Krokhin [46] proved that the complexity of the CSP depends only on the equational properties of the poly- morphism clone of the template. They proved that trivial equational properties imply hardness of the CSP, and conjectured that the CSP is solvable in polynomial time if the polymorphism clone of the template satisﬁes some nontrivial equation. It is this conjecture that Bulatov and Zhuk ﬁnally proved, relying on recent developments in universal algebra. As a by-product of the fact that the delineation between polynomial-time tractability and NP-hardness can be stated algebraically, we also obtain that the meta-problem for finite- domain CSPs is decidable. That is, there exists an algorithm that, given a ﬁnite relational structure A as input, decides the complexity of the CSP of A.
- Keywords (DE)
- Algebra, Klone, Komplexität
- Keywords (EN)
- Algebra, Clones, Complexity
- Classification (DDC)
- 510
- Classification (RVK)
- SK 240
- Awarding institution
- Technische Universität Dresden, Dresden
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-315310
- Qucosa date of publication
- 06.09.2018
- Document type
- doctoral_thesis
- Document language
- English
- licence