Theoretical Basis and Computational Complexity of Semifactual Explanations

Explainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we discuss the local post-hoc explainability queries for semifactual reasoning recently proposed in [1], analyze their computational complexity across different classification models, and examine the associated preference-based framework for semifactual and counterfactual explanations.