On the complexity of second-best abductive explanations

• Formal definition of second-best abductive solutions.
• Complexity depends on the ordering: is complete for Dp or Π2Π2.
• Checking solution and relevance of hypotheses.

When looking for a propositional abductive explanation of a given set of manifestations, an ordering between possible solutions is often assumed. While the complexity of computing optimal solutions is already known, in this paper we consider second-best solutions with respect to different orderings, and different definitions of what a second-best solution is: an optimal solution not already found, or a solution that is optimal among the ones not previously found.