The complexity of disjunctive linear Diophantine constraints - Bodirsky, Manuel; Mamino, Marcello; Martin, Barnaby; Mottet, Antoine (2018)
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.
EPrint Processing Status: Full text deposited in DRO