✦ LIBER ✦

Inclusion–exclusion for k-CNF formulas

✍ Scribed by Kazuyuki Amano; Kazuo Iwama; Akira Maruoka; Kenshi Matsuo; Akihiro Matsuura

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 120 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00259-x

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the number of satisfying assignments of a k-CNF formula is determined uniquely from the numbers of unsatisfying assignments for clause-sets of size up to log k + 2. This amount of information is also shown to be necessary.

📜 SIMILAR VOLUMES

Inclusion-Exclusion Formulas from Indepe

Inclusion-Exclusion Formulas from Independent Complexes

✍ Dominique Attali; Herbert Edelsbrunner 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 396 KB

A New Type of Inclusion Exclusion Princi

A New Type of Inclusion Exclusion Principle for Sequences and Asymptotic Formulas for ζ(k)

✍ S. Akiyama 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 384 KB

Generalizations of Matched CNF Formulas

✍ Stefan Szeider 📂 Article 📅 2005 🏛 Springer Netherlands 🌐 English ⚖ 179 KB

Generalizations of matched CNF formulas

✍ Stefan Szeider 📂 Article 📅 2004 🏛 Springer Netherlands 🌐 English ⚖ 188 KB

The satisfiability problem in regular CN

The satisfiability problem in regular CNF-formulas

✍ F. Manyà; R. Béjar; G. Escalada-Imaz 📂 Article 📅 1998 🏛 Springer 🌐 English ⚖ 319 KB

On an inclusion-exclusion formula based

On an inclusion-exclusion formula based on the reflection principle

✍ T Watanabe; S.G Monanty 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 385 KB

The n-candidate ballot problem corresponding to the standard Young tableau has been solved recently by Zeilberger (Discrete Math. 44 (1983) 325-326) by using the reflection p "rmciple. In this paper, a refinement of Zeilberger's approach is provided in which the reflection principle is formulated th