The complexity of disjunctive linear Diophantine constraints

DOI10.4230/LIPICS.MFCS.2018.33MaRDI QIDQ6303793arXivFDO

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

Publication date 3 July 2018

Published in arXiv

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2018.33

Mathematics Subject Classification ID

Logic in computer science (03B70) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

arXiv classification

cs.CCmath.LO

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.

This page was built for publication: The complexity of disjunctive linear Diophantine constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6303793)