A Note on Approximating Inclusion-Exclusion for k-CNF Formulas

Akihiro MATSUURA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.1   pp.100-102
Publication Date: 2005/01/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.1.100
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.