SEMANTICS AND COMPLEXITY OF ABDUCTION FROM DEFAULT THEORIES

Abductive reasoning (roughly speaking, find an explanation for observa tions 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, autoepis temic 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 th eories in default logic. In particular, we present a basic model of ab duction from default theories. Different modes of abduction are plausi ble, based on credulous and skeptical default reasoning; they appear u seful for different applications such as diagnosis and planning, Moreo ver, we thoroughly analyze the complexity of the main abductive reason ing tasks, namely finding an explanation, deciding relevance of a hypo thesis, and deciding necessity of a hypothesis. These problems are int ractable even in the propositional case, and we locate them into the a ppropriate slots of the polynomial hierarchy. However, we also present known classes of default theories for which abduction is tractable. M oreover, we also consider first-order default theories, based on domai n closure and the unique names assumption, In this setting, the abduct ion tasks are decidable, but have exponentially higher complexity than in the propositional case. (C) 1997 Elsevier Science B.V.