On computing all abductive explanations
Thomas Eiter, Kazuhisa Makino · 2002
We consider the computation of all respectively a polynomial subset of the explanations of an abductive query from a Horn theory, and pay particular attention to whether the query is a positive or negative letter, the explanation is based on lit-erals from an assumption set, and the Horn theory is rep-resented in terms of formulas or characteristic models. We derive tractability results, one of which refutes a conjecture by Selman and Levesque, as well as intractability results, and furthermore also semi-tractability results in terms of solvabil-ity in quasi-polynomial time. Our results complement previ-ous results in the literature, and elucidate the computational complexity of generating the set of explanations.