The complexity of constraint satisfaction problems
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
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
Originalsprache | Englisch |
---|---|
Titel | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 |
Redakteure/-innen | Ernst W. Mayr, Nicolas Ollinger |
Herausgeber (Verlag) | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Seiten | 2-9 |
Seitenumfang | 8 |
ISBN (elektronisch) | 9783939897781 |
Publikationsstatus | Veröffentlicht - 1 Feb. 2015 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Leibniz international proceedings in informatics : LIPIcs |
---|---|
Band | 30 |
ISSN | 1868-8969 |
Konferenz
Titel | 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 |
---|---|
Dauer | 4 - 7 März 2015 |
Stadt | Garching |
Land | Deutschland |
Externe IDs
ORCID | /0000-0001-8228-3611/work/142241106 |
---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Clones, Constraint satisfaction, Model theory, Temporal and spatial reasoning, Universal algebra