For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Note on Approximating Inclusion-Exclusion for k-CNF Formulas
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science)
k-CNF formulas, satisfying assignments, counting, inclusion-exclusion,
Full Text: PDF(78.3KB)
>>Buy this Article
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 log k + 2 already uniquely determines the number of satisfying assignments of k-CNF formulas. The proof was, however, only existential and no explicit procedure was presented. In this paper, we show that such a procedure exists.