Constraint satisfaction problems over the integers with successor
Research output: Contribution to book/conference proceedings/anthology/report › Conference contribution › Contributed › peer-review
Contributors
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), 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.
Details
| Original language | English |
|---|---|
| Title of host publication | Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings |
| Editors | Magnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama |
| Publisher | Springer Verlag |
| Pages | 256-267 |
| Number of pages | 12 |
| ISBN (print) | 9783662476710 |
| Publication status | Published - 2015 |
| Peer-reviewed | Yes |
Publication series
| Series | Lecture Notes in Computer Science, Volume 9134 |
|---|---|
| ISSN | 0302-9743 |
Conference
| Title | 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 |
|---|---|
| Duration | 6 - 10 July 2015 |
| City | Kyoto |
| Country | Japan |
External IDs
| ORCID | /0000-0001-8228-3611/work/142241111 |
|---|