Our Model of Abduction

We now formalize our model; for sake of simplicity, we first define abduction problems and then the notions of hypothesis and explanation.

Definition 2 (abduction problem)   A triple $\Pi=(\Sigma,\alpha,A)$ is called an abduction problem if $\Sigma$ and $\alpha$ are satisfiable propositional formulas and $A$ is a set of variables with $Var(\alpha),A\subseteq Var(\Sigma)$; $\Sigma$ is called the knowledge base of $\Pi$, $\alpha$ its query and $A$ its set of abducibles.

Definition 3 (hypothesis,explanation)   Let $\Pi=(\Sigma,\alpha,A)$ be an abduction problem. An hypothesis for $\Pi$ is a set of literals formed upon $A$ (seen as their conjunction), and an hypothesis $E$ for $\Pi$ is an explanation for $\Pi$ if $\Sigma\wedge E$ is satisfiable and $\Sigma\wedge E\models\alpha$. If no proper subconjunction of $E$ is an explanation for $\Pi$, $E$ is called a best explanation for $\Pi$.

Note that this framework does not allow one to specify that a variable must occur unnegated (resp. negated) in an explanation. We do not think this is a prohibiting restriction, since abducibles are intuitively meant to represent the variables whose values can be, e.g., modified, observed or repaired, and then no matter their sign in an explanation. But we note that it is a restriction, and that a more general framework can be defined where the abducibles are literals and the hypotheses, conjunctions of abducibles [Mar00].

We are interested in the computational complexity of computing a best explanation for a given abduction problem, or asserting there is none at all. Following the usual model, we establish complexities with respect to the size of the representations of $\Sigma$ and $\alpha$ and to the number of abducibles; for hardness results, the following associated decision problem is usually considered: is there at least one explanation for $\Pi$? Obviously, if this latter problem is hard, then the function problem also is.