Abduction{ from observations and a theory, nd using hypotheses an explanation for the observations { gained increasing interest during the last years. This form of reasoning has wide applicability in di erent areas of computer science; in particular, it has been recognized as an important principle of common-sense reasoning. In this paper, we de ne a general abduction model for logic programming, where the inference operator (i.e., the semantics to be applied on programs), can be speci ed by the user. Advanced forms of logic programming have been proposed as valuable tools for knowledge representation and reasoning. We show that logic programming semantics can be more meaningful for abductive reasoning than classical inference by providing examples from the area of knowledge representation and reasoning. The main part of the paper is devoted to an extensive study of the computational complexity of the principal problems in abductive reasoning, which are: Given an instance of an abduction problem (1) does the problem have solution (i.e., an explanation); (2) does a given hypothesis belong to some explanation; and (3) does a given hypothesis belong to all explanations. This problems are analyzed for di erent underlying logic programming semantics, namely, the well-founded semantics, the stable model semantics and the minimal model semantics, paying attention to normal and disjunctive logic programs for the case of propositional as well as function-free rst order programs. The main results are that the above abductive reasoning tasks on propositional logic programs populate the classes at the lower end of the polynomial hierarchy up to P 4 , and provide complete problems for a number of classes over the rst four levels of the hierarchy. Similar results are obtained in the rst-order case. This proves abduction from logic programs as a rich source of problems of varying complexity. A preliminary extended abstract of this paper appeared in the
REF studied the complexity of reasoning tasks in the abductive logic programming setting.
Abduction from Logic Programs: Semantics and Complexity
Theoretical Computer Science
Mathematics Computer Science