A short implicant of a CNF formula with many satisfying assignments

DOI10.1007/S00453-016-0125-ZMaRDI QIDQ727982zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A short implicant of a CNF formula with many satisfying assignments
• A fast deterministic algorithm for formulas that have many satisfying assignments
• Solving and sampling with many solutions
• Length of prime implicants and number of solutions of random CNF formulae
• Why almost all satisfiable k-CNF formulas are easy

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A constructive proof of the Lovász local lemma
• A constructive proof of the general Lovász local lemma
• A fast deterministic algorithm for formulas that have many satisfying assignments
• Deterministic algorithms for the Lovász local lemma
• Improved pseudorandom generators for depth 2 circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(3)

• Inclusion-exclusion for \(k\)-CNF formulas
• Solving and sampling with many solutions: satisfiability and other hard problems
• A short implicant of a CNF formula with many satisfying assignments

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727982)