A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable

DOI10.1137/S0895480104445745zbMath1115.68104arXivmath/0411167OpenAlexW2045502027MaRDI QIDQ3440269

Stefan Szeider, Shlomo Hoory

Publication date: 22 May 2007

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0411167

zbMATH Keywords

NP-completenessoccurrence of variablesunsatisfiable CNF formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Designs and configurations (05B99)

Related Items (6)

Disproof of the neighborhood conjecture with implications to SAT ⋮ How Many Conflicts Does It Need to Be Unsatisfiable? ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ XSAT and NAE-SAT of linear CNF classes ⋮ Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable ⋮ The Lovász Local Lemma and Satisfiability

This page was built for publication: A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable