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 2^{n} 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