Introduction

Abduction consists in searching for a plausible explanation for a given observation. For instance, if $p\models 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\rightarrow 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 [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].