Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details for Dr Barnaby Martin

Bodirsky, 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.

Author(s) from Durham

Abstract

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.