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: | |
| Look up in GoogleScholar |
