Consider any Boolean function F(X1XN) that has more than 2?Nd satisfying assignments and that can be expressed by a CNF formula with at most N1+e clauses for some 0">d0 and 0">e0 such that d+e is less than 1 (*). Then how many variables do we need to fix in order to satisfy F? In other words, what is the size of the shortest implicant of F? We show that for any F satisfying (*), one can always find some short partial assignment on which F evaluates to 1 by fixing N variables for some 0">0. That is, F has an implicant of size N. On the other hand, a lower bound for such is also shown in terms of d and e.We also discuss an algorithm for obtaining a short partial assignment, and we show a deterministic algorithm that finds a short partial assignment in O(2N) -time for some 1 . Note that this can be used as a subexponential-time algorithm for solving the CNF-SAT problem for any CNF formula satisfying (*).
展开▼
