Unsatisfiable CNF formulas contain many conflicts

DOI10.1007/978-3-642-45030-3_26MaRDI QIDQ2872092zbMATH OpenOpenAlexFDO

Authors D. Scheder

Publication date 14 January 2014

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

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_26

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• How Many Conflicts Does It Need to Be Unsatisfiable?
• Unsatisfiable linear CNF formulas are large and complex
• A threshold for unsatisfiability
• Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
• The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3

Cited in

(4)

• Disjoint DNF tautologies with conflict bound two
• How Many Conflicts Does It Need to Be Unsatisfiable?
• Theory and Applications of Satisfiability Testing
• Unsatisfiable linear CNF formulas are large and complex

This page was built for publication: Unsatisfiable CNF formulas contain many conflicts

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