Constraint satisfaction problems over the integers with successor

Publikationstyp
Conference Paper
Date Issued
2015-07
Sprache
English
Author(s)
Bodirsky, Manuel  
Martin, Barnaby  
Mottet, Antoine  
TORE-URI
http://hdl.handle.net/11420/12097
First published in
Lecture notes in computer science  
Number in series
9134 LNCS
Start Page
256
End Page
267
Citation
42nd International Colloquium on Automata, Languages and Programming (ICALP 2015)
Contribution to Conference
42nd International Colloquium on Automata, Languages and Programming, ICALP 2015  
Publisher DOI
10.1007/978-3-662-47672-7_21
Scopus ID
2-s2.0-84950120571
A distance constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over (Z; succ), i. e., over the integers with the successor function. Our main result says that every distance CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP in which case the computational complexity is not known in general.