On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI
Authors: André Artelt, Martin Olsen, Kevin Tierney
TMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | André Artelt EMAIL Faculty of Technology Bielefeld University, Germany Martin Olsen EMAIL Department of Business Development and Technology Aarhus University, Denmark Kevin Tierney EMAIL Department of Business Decisions and Analytics University of Vienna, Austria |
| Pseudocode | No | The paper discusses computational problems and their complexity, including proofs by reduction (e.g., 3-SAT reduction in Appendix A.2). However, it does not present any structured pseudocode or algorithm blocks for any method or procedure. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the described methodology, nor does it provide any links to a code repository. The Open Review link is for the peer review process. |
| Open Datasets | No | The paper is theoretical, focusing on computational complexity and inapproximability results. It does not conduct experiments on any specific datasets, thus there is no mention of datasets being publicly available or access information for them. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments or dataset evaluation, therefore no information regarding training/test/validation dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on computational complexity. It does not describe any experimental setup or the specific hardware used to run experiments. |
| Software Dependencies | No | The paper is theoretical, analyzing computational complexity. It does not mention any specific software dependencies or versions (e.g., programming languages, libraries, or solvers with version numbers) required for experimental reproduction. |
| Experiment Setup | No | The paper is theoretical, presenting computational complexity results and proofs. It does not include details on experimental setup such as hyperparameters, model initialization, or training schedules. |