# 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].

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