Complexity Results for Default Reasoning from Conditional Knowledge Bases

Abstract

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form "phi->psi", which informally read as "generally, if phi then psi". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their algorithmic properties only partial results are known so far. In this paper, we fill these gaps and draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default "phi->psi", does KB entail "phi->psi"? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment). We consider the general propositional case as well as syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). Furthermore, we analyze the effect of precomputing rankings for the respective approaches. Our results complement and extend previous results, and contribute in exploring the tractability / intractability frontier of default reasoning from conditional knowledge bases.