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
The Discrepancy of Unsatisfiable Matrices and a Lower Bound for the Komlós Conjecture Constant, Disproof of the neighborhood conjecture with implications to SAT, On the parameterized complexity of \((k,s)\)-SAT, Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma, 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