Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details for Dr Barnaby Martin

Bodirsky, Manuel, Mamino, Marcello, Martin, Barnaby & Mottet, Antoine (2018), The complexity of disjunctive linear Diophantine constraints, in Potapov, Igor, Spirakis, Paul & Worrell, James eds, Leibniz International Proceedings in Informatics (LIPIcs) 117: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Liverpool, UK, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 33:1--33:16.

Author(s) from Durham

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.