Paper Info
Title
The Complexity of Constraint Satisfaction Problems (Invited Talk).
Abstract
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.
Year
DOI
Venue
2015
10.4230/LIPIcs.STACS.2015.2
Leibniz International Proceedings in Informatics
Keywords
DocType
Volume
constraint satisfaction,universal algebra,model theory,clones,temporal and spatial reasoning
Conference
30
ISSN
Citations 
PageRank 
1868-8969
1
0.36
References 
Authors
0
1
Name
Order
Citations
PageRank
Manuel Bodirsky164454.63