** Next:** Previous Work
** Up:** Research Note: New Polynomial
** Previous:** Preliminaries

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

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 and and to the number of
abducibles; for hardness results, the following associated decision problem
is usually considered: is there at least one explanation for ?
Obviously, if this latter problem is hard, then the function problem
also is.

** Next:** Previous Work
** Up:** Research Note: New Polynomial
** Previous:** Preliminaries
Bruno Zanuttini
2003-06-30