The complexity of disjunctive linear Diophantine constraints

Bodirsky, Manuel; Mamino, Marcello; Martin, Barnaby; Mottet, Antoine

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.

Citation

Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018, August). The complexity of disjunctive linear Diophantine constraints. Presented at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
• Start Date: Aug 27, 2018
• End Date: Aug 31, 2018
• Acceptance Date: Jun 13, 2018
• Publication Date: Aug 31, 2018
• Deposit Date: Jul 12, 2018
• Publicly Available Date: Jul 13, 2018
• Volume: 117
• Pages: 33:1-33:16
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Series ISSN: 1868-8969
• Book Title: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK).
• DOI: https://doi.org/10.4230/lipics.mfcs.2018.33
• Public URL: https://durham-repository.worktribe.com/output/1146391