id:"swepub:oai:DiVA.org:liu-144455"
Search: id:"swepub:oai:DiVA.org:liu-144455" > Circuit satisfiabil...
- 1 of 1
- Previous record
- Next record
- To hitlist
- Glasser, ChristianJulius Maximilian University, Germany (author)
Circuit satisfiability and constraint satisfaction around Skolem Arithmetic
- Article/chapterEnglish2017
Publisher, publication year, extent ...
- ELSEVIER SCIENCE BV,2017
- printrdacarrier
Numbers
- LIBRIS-ID:oai:DiVA.org:liu-144455
- https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-144455URI
- https://doi.org/10.1016/j.tcs.2017.08.025DOI
Supplementary language notes
- Language:English
- Summary in:English
Part of subdatabase
- SwePubSwePub
Classification
Notes
- Funding Agencies|EPSRC [EP/L005654/1]; Swedish Research Council (VR) [621-2012-3239]
- 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.
Subject headings and genre
- NATURVETENSKAP Matematik Diskret matematik hsv//swe
- NATURAL SCIENCES Mathematics Discrete Mathematics hsv//eng
- Circuit satisfiability; Constraint satisfaction; Skolem Arithmetic; Computational complexity
Added entries (persons, corporate bodies, meetings, titles ...)
- Jonsson, PeterLinköpings universitet,Programvara och system,Tekniska fakulteten(Swepub:liu)petjo00 (author)
- Martin, BarnabyUniversity of Durham, England (author)
- Julius Maximilian University, GermanyProgramvara och system (creator_code:org_t)
Related titles
- In:Theoretical Computer Science: ELSEVIER SCIENCE BV703, s. 18-360304-39751879-2294
Internet link
Find in a library
- Theoretical Computer Science (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Glasser, Christi ...
- Jonsson, Peter
- Martin, Barnaby
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Mathematics
- and Discrete Mathema ...
- Articles in the publication
- Theoretical Comp ...
- By the university
- Linköping University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
