Unsatisfiable linear CNF formulas are large and complex

DOI10.4230/LIPICS.STACS.2010.2490MaRDI QIDQ3113785zbMATH OpenOpenAlexFDO

Authors D. Scheder

Publication date 23 January 2012

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_0760.html

zbMATH Keywords

extremal combinatoricsprobabilistic methodproof complexity

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On Linear CNF Formulas
• The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
• Linear CNF formulas and satisfiability
• Unsatisfiable CNF formulas contain many conflicts
• scientific article; zbMATH DE number 1775444

Cited in

(9)

• Linear CNF formulas and satisfiability
• Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms
• XSAT and NAE-SAT of linear CNF classes
• Unsatisfiable CNF formulas contain many conflicts
• scientific article; zbMATH DE number 3849198 (Why is no real title available?)
• How Many Conflicts Does It Need to Be Unsatisfiable?
• Disproof of the neighborhood conjecture with implications to SAT
• The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
• On Linear CNF Formulas

This page was built for publication: Unsatisfiable linear CNF formulas are large and complex

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