The complexity of disjunctive linear diophantine constraints

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung

Beitragende

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.

Details

OriginalspracheEnglisch
Titel43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Redakteure/-innenIgor Potapov, James Worrell, Paul Spirakis
Herausgeber (Verlag)Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770866
PublikationsstatusVeröffentlicht - 1 Aug. 2018
Peer-Review-StatusJa

Publikationsreihe

ReiheLeibniz international proceedings in informatics : LIPIcs
Band117
ISSN1868-8969

Konferenz

Titel43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Dauer27 - 31 August 2018
StadtLiverpool
LandGroßbritannien/Vereinigtes Königreich

Externe IDs

ORCID /0000-0001-8228-3611/work/142241079

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • Computational complexity, Constraint satisfaction, Presburger arithmetic