Algorithms for four variants of the exact satisfiability problem
2004 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 320, no 2-3, 373-394 p.Article in journal (Refereed) Published
We present four polynomial space and exponential time algorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120n) (where n is the number of variables) time algorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907n) time algorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193n) and O(1.2299n) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487n) time algorithm. We also present an O(1.2190n) time algorithm for the general problem of counting the number of models for EXACT SATISFIABILITY, presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. © 2004 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
2004. Vol. 320, no 2-3, 373-394 p.
3-Satisfiability, Algorithm, Computational complexity, Counting, Counting models, Counting problem, Exact 3-satisfiability, Exact satisfiability, Exact solution, Exponential-time algorithm, SAT, Satisfiability, X3SAT, XSAT
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-45713DOI: 10.1016/j.tcs.2004.02.035OAI: oai:DiVA.org:liu-45713DiVA: diva2:266609