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

Akihiro MATSUURA 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E88-D  No.1  pp.100-102
Publication Date: 2005/01/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section LETTER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
k-CNF formulas,  satisfying assignments,  counting,  inclusion-exclusion, 

Full Text: PDF(78.2KB)

Summary: 
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.