Publication details for Dr Barnaby MartinBodirsky, Manuel, Martin, Barnaby & Mottet, Antoine (2015), Constraint Satisfaction Problems over the Integers with Successor, in Halldórsson, Magnús M., Iwama, Kazuo, Kobayashi, Naoki & Speckmann, Bettina eds, Lecture Notes in Computer Science, 9134 Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. Kyoto, Japan, Springer, Berlin, 256-267.
- Publication type: Conference Paper
- ISSN/ISBN: 9783662476710, 9783662476727, 0302-9743, 1611-3349
- DOI: 10.1007/978-3-662-47672-7_21
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
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)(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.