zbMATH — the first resource for mathematics

Solving 3-satisfiability in less than \(1,579^ n\) steps. (English) Zbl 0788.68066
Börger, Egon (ed.) et al., Computer science logic. 6th workshop, CSL ’92, San Miniato, Italy, September 28 - October 2, 1992. Selected papers. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 702, 379-394 (1993).
Summary: We describe and analyse an improved algorithm for solving the 3- Satisfiability problem. If \(F\) is a Boolean formula in conjunctive normal form with \(n\) variables and \(r\) clauses, then we will show that this algorithm solves the Satisfiability problem for formulas with at most three literals per clause in time less than \(O(1,579^ n)\).
For the entire collection see [Zbl 0852.00039].

68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)