Satisfiability problems for propositional calculi

DOI10.1007/BF01744287zbMath0428.03035MaRDI QIDQ3864500

Harry R. Lewis

Publication date: 1979

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

NP-completenessBoolean connectivespolynomial-time satisfiability problemsatisfiability for formulas

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Related Items (24)

Parametrised Complexity of Satisfiability in Temporal Logic ⋮ Complexity of Model Checking for Modal Dependence Logic ⋮ The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I ⋮ A hierarchy of propositional Horn formuls ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ Generalized satisfiability for the description logic \(\mathcal{ALC}\) ⋮ Lewis dichotomies in many-valued logics ⋮ The complexity of satisfiability for fragments of hybrid logic. I. ⋮ On the applicability of Post's lattice ⋮ Complexity results for classes of quantificational formulas ⋮ Complexity results for modal dependence logic ⋮ Optimal satisfiability for propositional calculi and constraint satisfaction problems. ⋮ Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic ⋮ Generalized Satisfiability for the Description Logic $\mathcal{ALC}$ ⋮ Unnamed Item ⋮ THE COMPLEXITY OF MODEL CHECKING FOR BOOLEAN FORMULAS ⋮ The complexity of circumscriptive inference in Post's lattice ⋮ The Weight in Enumeration ⋮ Generalized modal satisfiability ⋮ The complexity of propositional implication ⋮ On the complexity of the clone membership problem ⋮ The Complexity of Reasoning for Fragments of Default Logic ⋮ The Complexity of Satisfiability for Fragments of CTL and CTL⋆ ⋮ The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments

Cites Work

• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Unnamed Item

This page was built for publication: Satisfiability problems for propositional calculi