The complexity of constraint satisfaction problems

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

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 languageEnglish
Title of host publication32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
EditorsErnst W. Mayr, Nicolas Ollinger
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages2-9
Number of pages8
ISBN (electronic)9783939897781
Publication statusPublished - 1 Feb 2015
Peer-reviewedYes

Publication series

SeriesLeibniz international proceedings in informatics : LIPIcs
Volume30
ISSN1868-8969

Conference

Title32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
Duration4 - 7 March 2015
CityGarching
CountryGermany

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