Constraint Satisfaction Problems over the Integers with Successor

Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine

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, July). Constraint Satisfaction Problems over the Integers with Successor. Presented at Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, Kyoto, Japan

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I
• 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: Oct 17, 2016
• Print ISSN: 0302-9743
• 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