Abstract
Let F = C 1 ∧ ⋯ ∧ C m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(20.18674n). Thereby we improve a result in [2,3] stating X3SAT ∈ O(20.2072n) and a bound of O(20.200002n) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SAT ∈ O(20.16254n).
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
V. Dahllöf and P. Jonson, Exact 3-Satisfiability — the decision and counting problems, Working Paper, Department of Computer and Information Science, Linköping University, Sweden (2002).
L. Drori and D. Peleg, Faster solutions for Exact Hitting and Exact SAT, Technical report MCS99-15, Weizmann Institute of Science, Israel (1999).
L. Drori and D. Peleg, Faster exact solutions for some NP-hard problems, in: Proceedings of the European Symposium on Algorithms (ESA 1999), Prague, Czech Republic, ed. J. Nesetril, Lecture Notes in Computer Science, Vol. 1643 (Springer, 1999) pp. 450–461.
L. Lovász and M. D. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol. 29 (North-Holland, 1986).
B. Monien, E. Speckenmeyer and O. Vornberger, Upper bounds for covering problems, Methods of Operations Research 43 (1981) 419–431.
T.J. Schaefer, The complexity of satisfiability problems, in: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, CA, 1–3 May 1978 (ACM, 1978) pp. 216–226.
Author information
Authors and Affiliations
Additional information
An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002).
Rights and permissions
About this article
Cite this article
Porschen, S., Randerath, B. & Speckenmeyer, E. Exact 3-satisfiability is decidable in time O(20.16254n). Ann Math Artif Intell 43, 173–193 (2005). https://doi.org/10.1007/s10472-005-0428-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-005-0428-2