A Note on Approximating Inclusion-Exclusion for k-CNF Formulas(<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 [1]. The proof was, however, only existential and no explicit procedure was presented. In this paper, we show that such a procedure exists.

• 社団法人電子情報通信学会の論文
• 2005-01-01

著者

• Matsuura Akihiro

  The Department Of Computers And Systerns Engineering Tokyo Denki University

関連論文

• A Note on Approximating Inclusion-Exclusion for k-CNF Formulas(Foundations of Computer Science)

スポンサーリンク