Hirsch, E. A., A Fast Deterministic Algorithm for Formulas That Have Many Satisfying Assignments.
Logic Journal of the IGPL, Vol.6, No.1, Oxford University Press, 1998, pp.59-71.

Abstract. How can we find any satisfying assignment for a Boolean formula that has many satisfying assignments? There exists an obvious randomized algorithm for solving this problem: one can just pick an assignment at random and check the truth value of the formula for this assignment, this is iterated until a satisfying assignment occurs. Does there exist a polynomial-time deterministic algorithm that solves the same problem? This paper presents such an algorithm and shows that its worst-case running time is linear when input formulas are in k-CNF and a fraction of satisfying assignments (among all possible assignments) is greater than a constant. This algorithm is almost the same as the algorithm proposed by Monien and Speckenmeyer (and independently by Dantsin) in the early 1980s for less than 2n steps 3-SAT decision. Another result of this paper is that if a formula in k-CNF has many satisfying assignments, then there exists a short satisfying assignment, i.e. an assignment of truth values to a small number of variables. The proposed algorithm yields just such a short satisfying assignment. We also show that there exist formulas in general CNF having many satisfying assignments, that have no short satisfying assignments.

Full text: [ .ps.gz (209 Kb) ]


Back to the list of papers