A note on approximating inclusion-exclusion for k-CNF formulas
The number of satisfying assignments of k-CNF formulas is computed using, the inclusion-exclusion formula for sets of clauses. Recently,it was shown that the information on the sets of clauses of size less than or equal to [log k] + 2 already uniquely determines the number of satisfying assignments of k-CNF formulas [1]. The proof was, however, only existential and no explicit procedure was presented. In this paper, we show that such a procedure exists.
k-cnf formulas satisfying assignments counting inclusion exclusion