On Linear CNF Formulas

DOI10.1007/11814948_22MaRDI QIDQ5756579zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

NP-completenesssatisfiabilityedge colouringLatin squarelinear hypergraphlinear CNF formula

Mathematics Subject Classification ID

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)

Recommendations

• Linear CNF formulas and satisfiability
• The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
• On Some SAT-Variants over Linear Formulas
• Unsatisfiable linear CNF formulas are large and complex
• Exact satisfiability of linear CNF formulas

Cited in

(18)

• On Some SAT-Variants over Linear Formulas
• scientific article; zbMATH DE number 7204396 (Why is no real title available?)
• scientific article; zbMATH DE number 5613969 (Why is no real title available?)
• scientific article; zbMATH DE number 810103 (Why is no real title available?)
• A CNF Class Generalizing Exact Linear Formulas
• XSAT and NAE-SAT of linear CNF classes
• The Existence of Unsatisfiable Formulas in k-LCNF for k ≥ 3
• The SAT problem of signed CNF formulas
• Exact satisfiability of linear CNF formulas
• A CNF Formula Hierarchy over the Hypercube
• Unsatisfiable linear CNF formulas are large and complex
• Trivial, tractable, hard. A not so sudden complexity jump in neighborhood restricted CNF formulas
• On the complexity of equational problems in CNF
• A linear-time transformation of linear inequalities into conjunctive normal form
• Linear CNF formulas and satisfiability
• The Lovász Local Lemma and Satisfiability
• Exponential complexity of satisfiability testing for linear-size Boolean 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)