Skip to main content

Research Repository

Advanced Search

The complexity of disjunctive linear Diophantine constraints

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

The complexity of disjunctive linear Diophantine constraints Thumbnail


Authors

Manuel Bodirsky

Marcello Mamino

Antoine Mottet



Contributors

Igor Potapov
Editor

Paul Spirakis
Editor

James Worrell
Editor

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). The complexity of disjunctive linear Diophantine constraints. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). August 27-31, 2018, Liverpool (UK) (33:1-33:16). https://doi.org/10.4230/lipics.mfcs.2018.33

Conference Name 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
Conference Location Liverpool, UK
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 Mar 29, 2024
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

Files






You might also like



Downloadable Citations