The complexity of disjunctive linear diophantine constraints

Publikationstyp
Conference Paper
Date Issued
2018-08
Sprache
English
Author(s)
Bodirsky, Manuel  
Martin, Barnaby  
Mamino, Marcello  
Mottet, Antoine  
TORE-URI
http://hdl.handle.net/11420/12093
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
117
Article Number
33
Citation
43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 117: 33 (2018)
Contribution to Conference
43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018  
Publisher DOI
10.4230/LIPIcs.MFCS.2018.33
Scopus ID
2-s2.0-85053200410
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
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.
Subjects
Computational complexity
Constraint satisfaction
Presburger arithmetic