DNF tautologies with a limited number of occurrences of every variable

DOI10.1016/S0304-3975(00)00036-0zbMath0944.68059OpenAlexW2044983583WikidataQ127706329 ScholiaQ127706329MaRDI QIDQ1575269

Jiří Sgall, Petr Savický

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00036-0

zbMATH Keywords

disjunctive normal formtautologyoccurrences of variable

Mathematics Subject Classification ID

Related Items (5)

Disproof of the neighborhood conjecture with implications to SAT ⋮ The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant ⋮ Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable ⋮ The Lovász Local Lemma and Satisfiability ⋮ Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma

Cites Work

• A simplified NP-complete satisfiability problem
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

This page was built for publication: DNF tautologies with a limited number of occurrences of every variable