Skip to main content

Research Repository

Advanced Search

Constraint Satisfaction Problems over the Integers with Successor

Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine

Constraint Satisfaction Problems over the Integers with Successor Thumbnail


Authors

Manuel Bodirsky

Antoine Mottet



Contributors

Magnús M. Halldórsson
Editor

Kazuo Iwama
Editor

Naoki Kobayashi
Editor

Bettina Speckmann
Editor

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.

Citation

Bodirsky, M., Martin, B., & Mottet, A. (2015). Constraint Satisfaction Problems over the Integers with Successor. In M. M. Halldórsson, K. Iwama, N. Kobayashi, & B. Speckmann (Eds.), Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015. Proceedings. Part I (256-267). https://doi.org/10.1007/978-3-662-47672-7_21

Conference Name Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I
Conference Location Kyoto, Japan
Start Date Jul 6, 2015
End Date Jul 10, 2015
Acceptance Date Apr 4, 2015
Online Publication Date Jun 20, 2015
Publication Date Jun 20, 2015
Deposit Date Oct 14, 2016
Publicly Available Date Mar 28, 2024
Pages 256-267
Series Title Lecture notes in computer science
Series Number 9134
Series ISSN 0302-9743,1611-3349
Book Title Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015. Proceedings. Part I.
ISBN 9783662476710
DOI https://doi.org/10.1007/978-3-662-47672-7_21
Public URL https://durham-repository.worktribe.com/output/1151081
Related Public URLs https://arxiv.org/abs/1503.08572v1

Files





You might also like



Downloadable Citations