A Short Implicant of a CNF Formula with Many Satisfying Assignments

DOI10.1007/978-3-319-13075-0_22zbMath1351.68118OpenAlexW297482899MaRDI QIDQ2942635

Osamu Watanabe, Daniel M. Kane

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100715512

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A constructive proof of the general lovász local lemma
• Improved Pseudorandom Generators for Depth 2 Circuits
• A fast deterministic algorithm for formulas that have many satisfying assignments
• A constructive proof of the Lovász local lemma
• Unnamed Item

This page was built for publication: A Short Implicant of a CNF Formula with Many Satisfying Assignments