Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Circuit satisfiability and constraint satisfaction around Skolem arithmetic.

Glaßer, Christian and Jonsson, Peter and Martin, Barnaby (2017) 'Circuit satisfiability and constraint satisfaction around Skolem arithmetic.', Theoretical computer science., 703 . pp. 18-36.

Abstract

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glaßer et al. [1] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits—involving complement, intersection, union and multiplication—to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [1] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, (N;×), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(413Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.tcs.2017.08.025
Publisher statement:© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:31 August 2017
Date deposited:12 September 2017
Date of first online publication:06 September 2017
Date first made open access:06 September 2018

Save or Share this output

Export:
Export
Look up in GoogleScholar