The complexity of constraint satisfaction problems

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

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

OriginalspracheEnglisch
Titel32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
Redakteure/-innenErnst W. Mayr, Nicolas Ollinger
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Seiten2-9
Seitenumfang8
ISBN (elektronisch)9783939897781
PublikationsstatusVeröffentlicht - 1 Feb. 2015
Peer-Review-StatusJa

Publikationsreihe

ReiheLeibniz international proceedings in informatics : LIPIcs
Band30
ISSN1868-8969

Konferenz

Titel32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
Dauer4 - 7 März 2015
StadtGarching
LandDeutschland

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