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

    • MATSUURA Akihiro
    • the Department of Computers and Systerns Engineering, Tokyo Denki University

Abstract

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.

Journal

IEICE transactions on information and systems   [List of Volumes]

IEICE transactions on information and systems E88-D(1), 100-102, 2005-01-01  [Table of Contents]

The Institute of Electronics, Information and Communication Engineers

References:  4

You must have a user ID to see the references.If you already have a user ID, please click "Login" to access the info.New users can click "Sign Up" to register for an user ID.

Preview

Preview

Codes

  • NII Article ID (NAID) :
    110003214141
  • NII NACSIS-CAT ID (NCID) :
    AA10826272
  • Text Lang :
    ENG
  • Article Type :
    SHO
  • ISSN :
    09168532
  • Databases :
    CJP  NII-ELS 

Share