On Linear CNF Formulas
DOI10.1007/11814948_22zbMATH Open1138.68551OpenAlexW1536155927MaRDI QIDQ5756579FDOQ5756579
Authors: Stefan Porschen, Ewald Speckenmeyer, Bert Randerath 
Publication date: 4 September 2007
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11814948_22
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Classical propositional logic (03B05) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)
Cited In (17)
- A CNF Class Generalizing Exact Linear Formulas
- Exponential complexity of satisfiability testing for linear-size Boolean formulas
- On the complexity of equational problems in CNF
- Title not available (Why is that?)
- Unsatisfiable linear CNF formulas are large and complex
- Exact satisfiability of linear CNF formulas
- A linear-time transformation of linear inequalities into conjunctive normal form
- XSAT and NAE-SAT of linear CNF classes
- Linear CNF formulas and satisfiability
- Title not available (Why is that?)
- On Some SAT-Variants over Linear Formulas
- The Lovász Local Lemma and Satisfiability
- A CNF Formula Hierarchy over the Hypercube
- Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
- The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
- The SAT problem of signed CNF formulas
- On extremal \(k\)-CNF formulas
This page was built for publication: On Linear CNF Formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756579)
