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. 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 O(2~(N~β) )-time for some β ＜ 1 for any CNF formula with at most N~(1+ε) clauses having more than 2~(-N~δ) · 2~N satisfying assignments. (This is an extended abstract, and some detailed explanations axe omitted; see for the details.).
展开▼
