License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.2
URN: urn:nbn:de:0030-drops-49567
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4956/
Go to the corresponding LIPIcs Volume Portal

Bodirsky, Manuel

The Complexity of Constraint Satisfaction Problems (Invited Talk)

pdf-format:
56.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bodirsky:LIPIcs:2015:4956,
  author =	{Manuel Bodirsky},
  title =	{{The Complexity of Constraint Satisfaction Problems (Invited Talk)}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{2--9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4956},
  URN =		{urn:nbn:de:0030-drops-49567},
  doi =		{10.4230/LIPIcs.STACS.2015.2},
  annote =	{Keywords: constraint satisfaction, universal algebra, model theory, clones, temporal and spatial reasoning}
}

Keywords: constraint satisfaction, universal algebra, model theory, clones, temporal and spatial reasoning
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI