# On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI

arXiv: https://arxiv.org/abs/2601.09455 · HTML: https://mlsanity.com/paper/2601.09455/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 14 Jan 2026.

## Builds on (most cited first, 28 of 28)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On the Fairness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2010.06529/) (2020)
- [On Generating Plausible Counterfactual and Semi-Factual Explanations for Deep Learning](https://mlsanity.com/paper/2009.06399/) (2020)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [Decisions, Counterfactual Explanations and Strategic Behavior](https://mlsanity.com/paper/2002.04333/) (2020)
- [Evaluating Robustness of Counterfactual Explanations](https://mlsanity.com/paper/2103.02354/) (2021)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [Convex Density Constraints for Computing Plausible Counterfactual Explanations](https://mlsanity.com/paper/2002.04862/) (2020)
- [Even if Explanations: Prior Work, Desiderata & Benchmarks for Semi-Factual XAI](https://mlsanity.com/paper/2301.11970/) (2023)
- [A Few Good Counterfactuals: Generating Interpretable, Plausible and Diverse Counterfactual Explanations](https://mlsanity.com/paper/2101.09056/) (2021)
- [FaiR-N: Fair and Robust Neural Networks for Structured Data](https://mlsanity.com/paper/2010.06113/) (2020)
- ["Even if ..." -- Diverse Semifactual Explanations of Reject](https://mlsanity.com/paper/2207.01898/) (2022)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- ["Explain it in the Same Way!" -- Model-Agnostic Group Fairness of Counterfactual Explanations](https://mlsanity.com/paper/2211.14858/) (2022)
- [The Utility of "Even if..." Semifactual Explanation to Optimise Positive Outcomes](https://mlsanity.com/paper/2310.18937/) (2023)
- [Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations](https://mlsanity.com/paper/2407.07482/) (2024)
- [Even-Ifs From If-Onlys: Are the Best Semi-Factual Explanations Found Using Counterfactuals As Guides?](https://mlsanity.com/paper/2403.00980/) (2024)
- [Even-if Explanations: Formal Foundations, Priorities and Complexity](https://mlsanity.com/paper/2401.10938/) (2024)

## Abstract (arXiv)

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.