Computing unsatisfiable \(k\)-SAT instances with few occurrences per variable
From MaRDI portal
Publication:557836
DOI10.1016/j.tcs.2005.02.004zbMath1087.68042MaRDI QIDQ557836
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
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Disproof of the neighborhood conjecture with implications to SAT, The Lovász Local Lemma and Satisfiability
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