A short implicant of a CNF formula with many satisfying assignments

DOI10.1007/S00453-016-0125-ZzbMATH Open1355.68122OpenAlexW2292871600MaRDI QIDQ727982FDOQ727982

Daniel M. Kane, Osamu Watanabe

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

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

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)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Title not available (Why is that?)
• A constructive proof of the general Lovász local lemma
• Improved pseudorandom generators for depth 2 circuits
• A constructive proof of the Lovász local lemma
• Title not available (Why is that?)
• A fast deterministic algorithm for formulas that have many satisfying assignments

Cited In (2)

• Solving and sampling with many solutions: Satisfiability and other hard problems
• Inclusion-exclusion for \(k\)-CNF formulas

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)