ABDUCTION FROM LOGIC PROGRAMS - SEMANTICS AND COMPLEXITY

Abduction - from observations and a theory, find using hypotheses an e xplanation for the observations - gained increasing interest during th e last years. This form of reasoning has wide applicability in differe nt areas of computer science; in particular, it has been recognized as an important principle of common-sense reasoning. In this paper, we d efine a general abduction model for logic programming, where the infer ence operator (i.e., the semantics to be applied on programs), can be specified by the user. Advanced forms of logic programming have been p roposed as valuable tools for knowledge representation and reasoning. We show that logic programming semantics can be more meaningful for ab ductive reasoning than classical inference by providing examples from the area of knowledge representation and reasoning. The main part of t he paper is devoted to an extensive study of the computational complex ity of the principal problems in abductive reasoning, which are: Given an instance of an abduction problem (1) does the problem have solutio n (i.e., an explanation); (2) does a given hypothesis belong to some e xplanation; and (3) does a given hypothesis belong to all explanations . This problems are analyzed for different underlying logic programmin g semantics, namely, the well-founded semantics, the stable model sema ntics and the minimal model semantics, paying attention to normal and disjunctive logic programs for the case of propositional as well as fu nction-free first-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 Sigma(4)(P ), and provide complete problems for a number of classes over the firs t four levels of the hierarchy. Similar results are obtained in the fi rst-order case. This proves abduction from logic programs as a rich so urce of problems of varying complexity.