Dichotomies in Constraint Satisfaction: Canonical Functions and Numeric CSPs

Research output: Types of ThesisDoctoral thesis

Contributors

Abstract

Constraint satisfaction problems (CSPs) form a large class of decision problems that con- tains numerous classical problems like the satisfiability 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 finite relational structure A, the template, gives rise to the decision problem of determining whether there exists a homomorphism from a finite 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 satisfies 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 confirmation 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 satisfies 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 satisfies some nontrivial equation. It is this conjecture that Bulatov and Zhuk finally 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 finite relational structure A as input, decides the complexity of the CSP of A

Details

Original languageUndefined
Publication statusPublished - 6 Sept 2018
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.Thesis

Keywords

Keywords

  • Algebra, Clones, Complexity, Algebra, Klone, Komplexität, info:eu-repo/classification/ddc/510, ddc:510