On the Complexity of Finding Second-Best Abductive Explanations
arXiv:1204.5859v35 citations
Originality Synthesis-oriented
AI Analysis
This work addresses a theoretical problem in AI and logic, but it is incremental as it extends existing complexity analyses to second-best scenarios.
The paper investigates the computational complexity of finding second-best abductive explanations under various orderings and definitions, building on known results for optimal solutions.
While looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we consider the computational complexity of finding second-best solutions. We consider different orderings, and consider also different possible definitions of what a second-best solution is.