Consider any Boolean function F (X_1,...,X_N) that has more than 2~(-N)~δ 2·N satisfying assignments for some δ, 0 < δ < 1, and that can be expressed by a CNF formula with at most N~d 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 αN variables for some constant α < 1; that is, F has an implicant of size ≤ αN. A lower bound for such α is also shown in terms of δ and d.
展开▼
