Unsatisfiable Linear CNF Formulas Are Large and Complex.

DOI10.4230/LIPIcs.STACS.2010.2490zbMath1230.68116OpenAlexW2962941898MaRDI QIDQ3113785

Dominik 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

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

Related Items (3)

Disproof of the neighborhood conjecture with implications to SAT ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ XSAT and NAE-SAT of linear CNF classes

This page was built for publication: Unsatisfiable Linear CNF Formulas Are Large and Complex.