Abduction consists in searching for a plausible explanation for a given
observation. For instance, if then is a plausible
explanation for the observation . More generally, abduction is the process
of searching for a set of facts (the *explanation*, here ) that,
conjointly with a given *knowledge base* (here
),
imply a given *query* (). 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 [HSAM93], system [CM98,SW01] or medical diagnosis [BATJ89, Section 6]. It is also closely related to configuration problems [AFM02], to the ATMS/CMS [RK87], to default reasoning [SL90] and even to induction [Goe97].

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 [EG95]. 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.

The note is organized as follows. We first recall the useful notions of propositional logic (Section 2), formalize the problem (Section 3) and briefly survey previous work about the complexity of abduction (Section 4). Then we give our algorithm (Section 5) and explore polynomial classes for it (Section 6). Finally, we discuss our results and perspectives (Section 7). For lack of space we cannot detail proofs, but a longer version of this work, containing detailed proofs and examples, is available [Zan03].