On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI

Generating explanations for AI decisions is often computationally difficult: The paper demonstrates that counterfactual and semifactual explanations—which show users what would need to change for a model to make a different decision—are "computationally hard" to produce in many real-world scenarios, meaning they require impractical amounts of computing time.

Even approximate explanations face fundamental barriers: The authors contribute new findings showing that not only are exact explanations hard to compute, but even simplified or approximate versions are difficult to generate under certain conditions, which limits practical workarounds to the computational challenge.

This complexity has real implications for AI regulation and deployment: The paper explicitly discusses how these computational hardness results affect both the XAI (explainable AI) research community and policymakers, suggesting that regulations requiring explanations may face technical feasibility challenges that need to be considered when designing AI governance frameworks.

The difficulty varies depending on the model type and explanation method: The paper reviews complexity results across the literature, indicating that some models and explanation approaches are harder to work with than others—meaning a one-size-fits-all approach to AI explainability may not be realistic.

There's a gap between what's theoretically desirable and what's practically achievable: The findings highlight a tension in responsible AI: while explanations are essential for trustworthy deployment in critical applications, the fundamental computational barriers mean organizations may struggle to provide them efficiently.