On some tractable classes in deduction and abduction

摘要

We address the identification of propositional theories for which entailment is tractable, so that every query about logical consequences of the theory can be answered in polynomial time. We map tractable satisfiability classes to tractable entailment classes, including hierarchies of tractable problems; and show that some initially promising conditions for tractability of entailment, proposed by Esghi (1993) and del Val (1994), surprisingly only identify a subset of renamable Horn.