UC San Diego

Consider any Boolean function F(X1,... ,XN) that has more than 2-Nδ. 2N satisfying assignments for some δ, 0 < δ < 1, and that can be expressed by a CNF formula with at most Nd clauses for some d > 0. Then how many variables do we need to fix in order to satisfy F? We show that one can always find some ‘short’ partial assignment on which F evaluates to 1 by fixing at most aN variables for some constant a < 1; that is, F has an implicant of size < aN. A lower bound for such a is also shown in terms of δ and d. We also discuss an algorithm for obtaining a short partial assignment. For any δ and ε such that 0 < δ + ε < 1, we show a deterministic algorithm that finds a short partial assignment in ȭ(2Nβ)-time for some β < 1 for any CNF formula with at most N1+ε clauses having more than 2 -2 satisfying assignments. (This is an extended abstract, and some detailed explanations are omitted; see [6] for the details.)