Semantics and complexity of abduction from default theories

摘要

Abductive reasoning (roughly speaking, find an explanation for observations out of hypotheses) has been recognized as an important principle of common-sense reasoning. Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories (i.e., knowledge bases) of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. In particular, we present a basic model of abduction from default theories. Different modes of abduction are plausible, based on credulous and skeptical default reasoning; they appear useful for different applications such as diagnosis and planning. Moreover, we thoroughly analyze the complexity of the main abductive reasoning tasks, namely finding an explanation, deciding relevance of a hypothesis and deciding necessity of a hypothesis. These problems are intractable even in the prepositional case and we locate them into the appropriate slots of the polynomial hierarchy. However, we also present known classes of default theories for which abduction is tractable. Moreover, we also consider first-order default theories, based on domain closure and the unique names assumption. In this setting, the abduction tasks are decidable, but have exponentially higher complexity than in the propositional case.