In this talk, we consider the problem of computing multiple explanations, and in particular all explanations for an abductive query from a propositional Horn theory. Our study pays particular attention to the form of the query, ranging from a literal to a compound formula, to whether explanations are based on a set of abducible literals, and to the representation of the Horn theory, either by a Horn CNF or model-based in terms of its characteristic models. For all these combinations, we present either tractability results in terms of polynomial total-time algorithms, intractability results in terms of nonexistence of such algorithms (unless P=NP), or semi-tractability results in terms of solvability in quasi-polynomial time, established by polynomial-time equivalence to the problem of dualizing a monotone conjunctive normal form expression. Our results complement previous results in the literature, and refute a longstanding conjecture by Selman and Levesque. They elucidate the complexity of generating all abductive explanations, and shed light on the related problems such as generating sets of restricted prime implicates of a Horn theory. The algorithms for tractable cases can be readily applied for generating a polynomial subset of explanations in polynomial time.

(Joint work with Thomas Eiter)