The complexity of constraint satisfaction problems
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
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.
Details
Original language | English |
---|---|
Title of host publication | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 |
Editors | Ernst W. Mayr, Nicolas Ollinger |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Pages | 2-9 |
Number of pages | 8 |
ISBN (electronic) | 9783939897781 |
Publication status | Published - 1 Feb 2015 |
Peer-reviewed | Yes |
Publication series
Series | Leibniz international proceedings in informatics : LIPIcs |
---|---|
Volume | 30 |
ISSN | 1868-8969 |
Conference
Title | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 |
---|---|
Duration | 4 - 7 March 2015 |
City | Garching |
Country | Germany |
External IDs
ORCID | /0000-0001-8228-3611/work/142241106 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- Clones, Constraint satisfaction, Model theory, Temporal and spatial reasoning, Universal algebra