2026-07-22T08:35:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4956 2024-03-06T10:35:30Z ddc:004 open_access

The Complexity of Constraint Satisfaction Problems (Invited Talk) Bodirsky, Manuel constraint satisfaction universal algebra model theory clones temporal and spatial reasoning The tractability conjecture for constraint satisfaction problems (CSPs) describes the constraint languages over a finite domain whose CSP can be solved in polynomial-time. The precise formulation of the conjecture uses basic notions from universal algebra. In this talk, we give a short introduction to the universal-algebraic approach to the study of the complexity of CSPs. Finally, we discuss attempts to generalise the tractability conjecture to large classes of constraint languages over infinite domains, in particular for constraint languages that arise in qualitative temporal and spatial reasoning. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.2 urn:nbn:de:0030-drops-49567 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.2 eng https://creativecommons.org/licenses/by/3.0/legalcode