# Research Note New Polynomial Classes For Logic-Based Abduction

Bruno  Zanuttini GREYC, Université de Caen, Boulevard du Maréchal Juin 14032 Caen Cédex, France ZANUTTIQINFO. UNICAEN.FR

## Abstract

We address the problem of propositional logic-based abduction, i.e., the problem of searching for a best explanation for a given propositional observation according to a given propositional knowledge base. We give a general algorithm, based on the notion of projection; then we study restrictions over the representations of the knowledge base and of the query, and find new polynomial classes of abduction problems.

## 1. Introduction

Abduction consists in searching for a plausible explanation for a given observation.  For instance, if p = q then p is a plausible explanation for the observation q . More generally, abduction is the process of searching for a set of facts ( the explanation, here p ) that, conjointly with a given knowledge base (here p → q ), imply a given query (q). This process is also constrained by a set of hypotheses among which the explanations have to be chosen, and by a preference criterion among them.

The problem of abduction proved its practical interest in many domains.  For instance, it has been used to formalize text interpretation (Hobbs et al., 1993), system (Coste-Marquis
& Marquis, 1998; Stumptner & Wotawa, 2001) or medical diagnosis (Bylander et al., 1989, Section 6). It is also closely related to configuration problems (Amilhastre et al., 2002), to the ATMS/CMS (Reiter & de Kleer, 1987), to default reasoning (Selman & Levesque, 1990) and even to induction (Goebel, 1997).

We are interested here in the complexity of propositional logic-based abduction, i.e., we assume both the knowledge base and the query are represented by propositional formulas.

Even in this framework, many different formalizations have been proposed in the literature, mainly differing about the definition of an hypothesis and that of a best explanation (Eiter & Gottlob, 1995). We assume here that the hypotheses are the conjunctions of literals formed upon a distinguished subset of the variables involved, and that a best explanation is one no proper subconjunction of which is an explanation ( subset-minimality criterion).

Our purpose is to exhibit new polynomial classes of abduction problems.  We give a general algorithm for finding a best explanation in the framework defined above, independently from the syntactic form of the formulas representing the knowledge base and the query. Then we explore the syntactic forms that allow a polynomial running time for this algorithm. We find new polynomial classes of abduction problems, among which the one restricting the knowledge base to be given as a Horn DNF and the query as a positive CNF,
and the one restricting the knowledge base to be given as an affine formula and the query as a disjunction of linear equations. Our algorithm also unifies several previous such results.