Classical propositional logic (03B05) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Recommendations
Cited in
(19)- Linear CNF formulas and satisfiability
- Satisfiability of co-nested formulas
- On the complexity of equational problems in CNF
- Exact satisfiability of linear CNF formulas
- XSAT and NAE-SAT of linear CNF classes
- On extremal \(k\)-CNF formulas
- The SAT problem of signed CNF formulas
- Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
- A linear-time transformation of linear inequalities into conjunctive normal form
- Unsatisfiable linear CNF formulas are large and complex
- scientific article; zbMATH DE number 5613969 (Why is no real title available?)
- A CNF Class Generalizing Exact Linear Formulas
- On Some SAT-Variants over Linear Formulas
- The Lovász Local Lemma and Satisfiability
- scientific article; zbMATH DE number 810103 (Why is no real title available?)
- Exponential complexity of satisfiability testing for linear-size Boolean formulas
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- A CNF Formula Hierarchy over the Hypercube
- The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
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)
