A short implicant of a CNF formula with many satisfying assignments

DOI10.1007/s00453-016-0125-zzbMath1355.68122OpenAlexW2292871600MaRDI QIDQ727982

Osamu Watanabe, Daniel M. Kane

Publication date: 21 December 2016

Published in: Algorithmica (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

zbMATH Keywords

conjunctive normal form formulalarge satisfying assignment ratioshort satisfying partial assignment

Mathematics Subject Classification ID

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

Related Items (1)

Solving and sampling with many solutions: Satisfiability and other hard problems

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
• Unnamed Item

This page was built for publication: A short implicant of a CNF formula with many satisfying assignments