On the complexity of second-best abductive explanations

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.

 @article{libe-scha-15,
 title = {On the complexity of second-best abductive explanations},
 year = {2015},
 author = {Paolo Liberatore and Marco Schaerf},
 journal = {International Journal of Approximate Reasoning},
 pages = {22-31},
 volume = {63},
 }