License
When quoting this document, please refer to the following
DOI: 10.4230/DFU.Vol7.15301.79
URN: urn:nbn:de:0030-drops-69580
URL: http://drops.dagstuhl.de/opus/volltexte/2017/6958/
Go to the corresponding DFU Volume Portal


Bodirsky, Manuel ; Mamino, Marcello

Constraint Satisfaction Problems over Numeric Domains

pdf-format:
DFU-Vol7-15301-3.pdf (0.6 MB)


Abstract

We present a survey of complexity results for constraint satisfaction problems (CSPs) over the integers, the rationals, the reals, and the complex numbers. Examples of such problems are feasibility of linear programs, integer linear programming, the max-atoms problem, Hilbert's tenth problem, and many more. Our particular focus is to identify those CSPs that can be solved in polynomial time, and to distinguish them from CSPs that are NP-hard. A very helpful tool for obtaining complexity classifications in this context is the concept of a polymorphism from universal algebra.

BibTeX - Entry

@InCollection{bodirsky_et_al:DFU:2017:6958,
  author =	{Manuel Bodirsky and Marcello Mamino},
  title =	{{Constraint Satisfaction Problems over Numeric Domains}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{79--111},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Andrei Krokhin and Stanislav Zivny},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6958},
  URN =		{urn:nbn:de:0030-drops-69580},
  doi =		{10.4230/DFU.Vol7.15301.79},
  annote =	{Keywords: Constraint satisfaction problems, Numerical domains}
}

Keywords: Constraint satisfaction problems, Numerical domains
Seminar: The Constraint Satisfaction Problem: Complexity and Approximability
Issue Date: 2017
Date of publication: 14.02.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI