Manuel Bodirsky
The complexity of disjunctive linear Diophantine constraints
Bodirsky, Manuel; Mamino, Marcello; Martin, Barnaby; Mottet, Antoine
Authors
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 | 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 |
Files
Accepted Conference Proceeding
(501 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© M. Bodirsky et al.; licensed under Creative Commons License CC-BY.
Published Conference Proceeding
(499 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search