On the complexity of second-best abductive explanations

Paolo Liberatore and Marco Schaerf

International Journal of Approximate Reasoning

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.

 title = {On the complexity of second-best abductive
 year = {2015},
 author = {Paolo Liberatore and Marco Schaerf},
 journal = {International Journal of Approximate Reasoning},
 pages = {22--31},
 volume = {63},
doi: 10.1016/j.ijar.2015.05.009