A hierarchy of tractable satisfiability problems

DOI10.1016/0020-0190(92)90081-6zbMath0774.68057OpenAlexW2080416548MaRDI QIDQ1208436

Mukesh Dalal, David W. Etherington

Publication date: 16 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90081-6

zbMATH Keywords

propositional satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35)

Related Items (13)

Properties of SLUR Formulae ⋮ On computing minimal models ⋮ Hierarchies of polynomially solvable satisfiability problems ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ Special issues on The satisfiability problem (pp. 1--244) including papers from the 1st workshop on satisfiability, Certosa di Pontignano, Italy, April 29--May 3, 1996 and Boolean functions (pp. 245--479) ⋮ On \(k\)-positive satisfiability problem ⋮ On some tractable classes in deduction and abduction ⋮ Classic learning ⋮ About some UP-based polynomial fragments of SAT ⋮ Solving the resolution-free SAT problem by submodel propagation in linear time ⋮ Present and Future of Practical SAT Solving ⋮ Tractable reasoning via approximation ⋮ A perspective on certain polynomial-time solvable classes of satisfiability

Cites Work

• An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences
• Polynomially solvable satisfiability problems
• The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On the Complexity of Timetable and Multicommodity Flow Problems
• The complexity of theorem-proving procedures

This page was built for publication: A hierarchy of tractable satisfiability problems