Sökning: id:"swepub:oai:DiVA.org:liu-144455" >
Circuit satisfiabil...
Circuit satisfiability and constraint satisfaction around Skolem Arithmetic
-
- Glasser, Christian (författare)
- Julius Maximilian University, Germany
-
- Jonsson, Peter (författare)
- Linköpings universitet,Programvara och system,Tekniska fakulteten
-
- Martin, Barnaby (författare)
- University of Durham, England
-
(creator_code:org_t)
- ELSEVIER SCIENCE BV, 2017
- 2017
- Engelska.
-
Ingår i: Theoretical Computer Science. - : ELSEVIER SCIENCE BV. - 0304-3975 .- 1879-2294. ; 703, s. 18-36
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Glasser 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; x), 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. (C) 2017 Elsevier B.V. All rights reserved.
Ämnesord
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Nyckelord
- Circuit satisfiability; Constraint satisfaction; Skolem Arithmetic; Computational complexity
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas