The complexity of disjunctive linear diophantine constraints
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
We study the Constraint Satisfaction Problem CSP(A), where A is first-order definable in (Z; +, 1) and contains +. We prove such problems are either in P or NP-complete.
Details
| Original language | English |
|---|---|
| Title of host publication | 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 |
| Editors | Igor Potapov, James Worrell, Paul Spirakis |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (print) | 9783959770866 |
| Publication status | Published - 1 Aug 2018 |
| Peer-reviewed | Yes |
Publication series
| Series | Leibniz international proceedings in informatics : LIPIcs |
|---|---|
| Volume | 117 |
| ISSN | 1868-8969 |
Conference
| Title | 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 |
|---|---|
| Duration | 27 - 31 August 2018 |
| City | Liverpool |
| Country | United Kingdom |
External IDs
| ORCID | /0000-0001-8228-3611/work/142241079 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- Computational complexity, Constraint satisfaction, Presburger arithmetic