Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.tcs.2021.07.036
DC Field | Value | |
---|---|---|
dc.title | Improved algorithms for the general exact satisfiability problem | |
dc.contributor.author | Hoi, G | |
dc.contributor.author | Stephan, F | |
dc.date.accessioned | 2023-07-24T08:37:00Z | |
dc.date.available | 2023-07-24T08:37:00Z | |
dc.date.issued | 2021-10-08 | |
dc.identifier.citation | Hoi, G, Stephan, F (2021-10-08). Improved algorithms for the general exact satisfiability problem. Theoretical Computer Science 889 : 60-84. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2021.07.036 | |
dc.identifier.issn | 0304-3975 | |
dc.identifier.uri | https://scholarbank.nus.edu.sg/handle/10635/243369 | |
dc.description.abstract | The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a Cj clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called GiXSAT as the problem to check whether a given instance consisting of Cj clauses with j∈{0,1,…,i} for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve GiXSAT, for i∈{2,3,4}, in O(1.3674n) time, O(1.5687n) time and O(1.6545n) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O(1.4203n) time for G2XSAT by Zhou, Jiang and Yin and from O(1.6202n) time for G3XSAT by Dahllöf and from O(1.6844n) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O(1.3188n) time, O(1.3407n) time and O(1.3536n) time respectively at the expense of using exponential space. | |
dc.publisher | Elsevier BV | |
dc.source | Elements | |
dc.subject | cs.DS | |
dc.subject | cs.DS | |
dc.type | Article | |
dc.date.updated | 2023-07-21T05:43:39Z | |
dc.contributor.department | MATHEMATICS | |
dc.description.doi | 10.1016/j.tcs.2021.07.036 | |
dc.description.sourcetitle | Theoretical Computer Science | |
dc.description.volume | 889 | |
dc.description.page | 60-84 | |
dc.published.state | Published | |
Appears in Collections: | Staff Publications Elements |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
2101.08637v2.pdf | Accepted version | 409.93 kB | Adobe PDF | OPEN | Pre-print | View/Download |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.