文章基本信息

标题：The Complexity of Disjunctive Linear Diophantine Constraints
本地全文：下载
作者：Manuel Bodirsky ; Barnaby Martin ; Marcello Mamino 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：117
页码：1-16
DOI：10.4230/LIPIcs.MFCS.2018.33
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Constraint Satisfaction; Presburger Arithmetic; Computational Complexity