Inclusion-exclusion for \(k\)-CNF formulas

DOI10.1016/S0020-0190(03)00259-XzbMath1161.68782OpenAlexW2059563384MaRDI QIDQ1014406

Kenshi Matsuo, Akihiro Matsuura, Kazuyuki Amano, Kazuo Iwama, Akira Maruoka

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00259-x

zbMATH Keywords

combinatorial problemscountingSATinclusion-exclusion\(k\)-CNF formula

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• The complexity of computing the permanent
• A note on approximate inclusion--exclusion
• Approximate inclusion-exclusion
• Counting propositional models
• Inclusion-exclusion: exact and approximate
• CNF-Satisfiability Test by Counting and Polynomial Average Time