On the applicability of Post's lattice

DOI10.1016/j.ipl.2012.02.002zbMath1243.68193arXiv1007.2924OpenAlexW1859310323MaRDI QIDQ436335

J. Herrera, H. S. Yoon

Publication date: 20 July 2012

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

Full work available at URL: https://arxiv.org/abs/1007.2924

zbMATH Keywords

computational complexityPost's lattice

Mathematics Subject Classification ID

Related Items (1)

The connectivity of Boolean satisfiability: dichotomies for formulas and circuits

Cites Work

• Unnamed Item
• The complexity of Boolean formula minimization
• The complexity of satisfiability for fragments of hybrid logic. I.
• The complexity of propositional implication
• Size-depth tradeoffs for Boolean formulae
• The Complexity of Reasoning for Fragments of Autoepistemic Logic
• Model Checking CTL is Almost Always Inherently Sequential
• THE COMPLEXITY OF MODEL CHECKING FOR BOOLEAN FORMULAS
• The Complexity of Reasoning for Fragments of Default Logic
• The Complexity of Circumscriptive Inference in Post’s Lattice
• THE COMPLEXITY OF SATISFIABILITY FOR FRAGMENTS OF CTL AND CTL⋆
• Satisfiability problems for propositional calculi
• The Parallel Evaluation of General Arithmetic Expressions
• The Tractability of Model-checking for LTL: The Good, the Bad, and the Ugly Fragments
• Mathematical Foundations of Computer Science 2003
• Generalized Modal Satisfiability
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: On the applicability of Post's lattice