Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

The complexity of disjunctive linear Diophantine constraints.

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:
Export
Look up in GoogleScholar