Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable

DOI10.1016/J.TCS.2005.02.004zbMath1087.68042OpenAlexW1979831715MaRDI QIDQ557836

Shlomo Hoory, Stefan Szeider

Publication date: 30 June 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.02.004

zbMATH Keywords

complexityinteger sequencesNP-completeness\((k,s)\)-SATunsatisfiable formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

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 ⋮ On the parameterized complexity of \((k,s)\)-SAT ⋮ 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
• Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
• An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF
• Satisfiability of co-nested formulas
• On the structure of some classes of minimal unsatisfiable formulas
• Homomorphisms of conjunctive normal forms.
• DNF tautologies with a limited number of occurrences of every variable
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable

This page was built for publication: Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable