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.
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.  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  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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (413Kb)
|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
|Look up in GoogleScholar|