Bodirsky, Manuel and Mamino, Marcello and Martin, Barnaby and Mottet, Antoine (2018) 'The complexity of disjunctive linear Diophantine constraints.', in 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 33:1-33:16. Leibniz International Proceedings in Informatics (LIPIcs)., 117
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.
| Item Type: | Book chapter |
|---|---|
| Full text: | (AM) Accepted Manuscript Available under License - Creative Commons Attribution. Download PDF (490Kb) |
| Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (488Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.4230/LIPIcs.MFCS.2018.33 |
| Publisher statement: | © M. Bodirsky et al.; licensed under Creative Commons License CC-BY. |
| Date accepted: | 13 June 2018 |
| Date deposited: | 13 July 2018 |
| Date of first online publication: | 2018 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
