On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI
This work highlights a fundamental challenge for XAI practitioners and policymakers aiming to ensure reliable and efficient explanations in critical AI applications.
The paper tackles the computational difficulty of generating counterfactual and semifactual explanations in explainable AI (XAI), finding that these tasks are often computationally hard and, under certain assumptions, even hard to approximate.
Providing clear explanations to the choices of machine learning models is essential for these models to be deployed in crucial applications. Counterfactual and semi-factual explanations have emerged as two mechanisms for providing users with insights into the outputs of their models. We provide an overview of the computational complexity results in the literature for generating these explanations, finding that in many cases, generating explanations is computationally hard. We strengthen the argument for this considerably by further contributing our own inapproximability results showing that not only are explanations often hard to generate, but under certain assumptions, they are also hard to approximate. We discuss the implications of these complexity results for the XAI community and for policymakers seeking to regulate explanations in AI.