On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI
Authors: André Artelt
Martin Olsen
Kevin Tierney
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (12/2025)
On the Hardness of Computing Counterfactual and Semi- factual Explanations in XAI
André Artelt
carteltsteehfol.mm--beeee de
Faculty of Technology
Bielefeld University, Germany
Martin Olsen
martino ou,
Department Business Development and Technology Aorhus University, Denmark
Kevin Tierney
kevin. www.nntttrree@@uniiiiiie ac.aa
Department of Business Decisions and Analytics University of Vienna, Austria
Reviewed on OpenReview: https: oppnrevvee.. net/ forum? id- aELzBuOq10
Abstract
Providing clear explanations to the choices of machine learming models is essential for these models to be deployed 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 the computational complexity results in the literature for generating these explanations, finding that in many cases, generating explanations is compu- tationally 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 secking to regulate explanations in AI.
1 Introduction
As machine learning (ML) models are increasingly used in critical applications, the ability to provide explana- tions about their outputs becomes crucially important. The FU AT Act (Furopean Parliament and Council of the European Union 2024) adds a regulatory motivation to enabling the explanation of models, as it "gives those subject to algorithmic decision the right to explanation of that decision" (Nisevic et al. 2024b. The field of explainable artificial intelligence (XAT) has emerged to address these challenges (Samek
& Müller 2019
Minh et al. )021).
However, despite the focus on providing explanations both in the research community and regulatory bodics, the computational complexity of explanations has only just begun to be explored. This raises the rentral question of this work, namely, under what conditions can we obtain explanations and in what computational complexity? The answer this question has an impact beyond the research domain, potentially affecting the feasibility of future laws and regulation concerning explainability in AI (Verma et al. 2024a).
One key focus of the XAI community is on counterfactual explanations (Guidotti 2024 which describe how changing the input features to an ML model changes the output prediction of this model. An alternative to counterfactual explanations are semi-factual explanations (Aryal 2024), which highlight changes in input features that do not lead to changes the model output. Both of these types of explanations allow users of models to understand how changing input affects their model, providing increased transparency, trust and potentially better decision making.

---

Published in Transactions on Machine Learning Research (12/2025)
The computational complexity of generating counterfactual and semi-factual explanations varies greatly depending on the MT. model and type of explanation desired, and in many cases is unknown. The literature has recently made great strides in defining various cases of explanations and providing proofs of computational complexity. However, the literature is split between different communitics, using different terminology and different formalizations, making it challenging to get a comprehensive overview. In particular, there no unifying framework to unify the many directions of research to give full view of the current state of the complexity of explanations.
This paper aims to resolve this and provides the following contribution.
1. We provide a comprehensive and accessible overview of the literature analyzing the computational complexity of counterfactual and semi-factual explanations.
2. We study the existence of approximation algorithms in several explanation settings, further refining the existing knowledge of the complexity of explanations.
3. We provide a critical discussion of our findings and what they mean for the XAI community.
This paper is organized as follows. We first provide some background about counterfactual explanations and foundations computational complexity Section 2 Next, we provide a framework of the complexity of explanations for various types of ML models, detailing both what we currently know and open challenges in Section 3 In Section 4 we provide novel approximation results for some explanation settings, whereby all proofs can be found in Appendix A.2 Finally, in Section
5 we discuss open questions and implications of computational complexity analysis for the XAT community.
2
Background & Foundations
2.1
Counterfactual & Semi-factual Explanations
A counterfactual explanation (CFE), often referred to simply as a counterfactual, outlines the specific changes that can be made to the features of a particular instance to alter the system's 's output. Typically, such expla- nations are sought when the outcome is unexpected or unfavorable (Riveiro & Thill 2022). In the latter case, a counterfactual is also referred as (computational) recourse (Karimi al.) 20.3). i.e. recommendations on how to change the unfavorable into favorable outcome. Because counterfactuals can mimic ways in which they constitute one of the most popular explanation methods in literature
humans explain (Byrne] 2019).
and in practice MMolnar 2019 Verma et al. 2024a).
Counterfactual explanations Wachter et al. 2017) have two key charactoristics: 1) the contrasting property, which necessitates a change in the system's output, and 2) the cost of the counterfactual, meaning the effort and resources required implement the counterfactual in the real world should be minimized to enhance its practicality. This often involves making as few changes as possible or ensuring that the changes are minimal. Both properties can be combined into optimization problem (see Definition D.
Definition 1 ((Classic) Counterfactual Explanation). Assume a classifier (binary or mulli-class) h y is given. Computing counterfactual def for a given instance Dorig X is phrased as the following optimization problem:
arg argmin min ((de)) 8.1. h(Korig @ des) = Yef
daf
where 8(-) denotes the cost of the explanation (e.g., cost of recourse) that should be minimized. We refer to the fenal counterfactual sample worig @ def as Tef.-
Remark 1. An alternative to the constrained optimization problem Eg. 1 is to use a single objective weighting the contrastive and cost properties as proposed by Wachter et al. (201 7
argmin E(h(2orig @ 6.)). ver) + X 8(6,)) det
(2)
2

---

Published in Transactions on Machine Learning Research (12/2025)
where X > 0 denotes regularization parometer that balances the two objectives, and E()) denotes suitable loss function such as the zero-one loss or the squared error in the case that h((.) denoles a regressor instead of a classifier.
To not make any assumptions on the data domain, we use the symbol @ to denote the poplication/exeeuttinn of the counterfactual bet to the original instance Zorig. While in the case of real and integer numbers (e.g.. X' = I this reduces to a translation, iee, (aret): = (Forig) + (det), in the case of categorical features it denotes a substitution, i.e. (æa) (6e)s
Note that the cost of the counterfactual (often also referred to as the cost of recourse), here modeled by (()), is highly domain and use-case-speciffe It therefore must be chosen carefully in practice, and might require domain knowledge. In many implementations and toolboxes [Guidotti] 2024), the p-norm is used as a default.
Besides those two essential properties (contrasting and cost), additional relevant aspects exist such as plausi-
bility (Artelt & Hammer
2020
Van Looveren & Klaise 2021 Poyiadzi et al.] 2020). diversity (Mothilal al.
2020), robustness (w.r.t.
to input perturbations or model changes) (Artelt el al. 2021 Zhang et al.] 2023
Leofante & Potyka| 2024
Marzari et al., 2024h, and fairness (Artelt & Hammer 2023
von Kügelgen et al. 2020), which have been addressed in literature (Guidotti 2024). In particular,
2022 Sharma et al.
2021
robustness with respect to model changes has recently received significant attention (Marzari et al. 2024
Leofante & Wicker 2025). Here, a set (H) is assumed that contains all plausible variations/changer of a
given classifier 1(-). We can then extend Eq. [ for computing a counterfactual det that is robust under those
model changes AH(h) as follows (Marzari al. 2024):
arg min 0(5xt) s.L. h (aarig @ dct) = yer wh' E AH(h) &at
(3)
However, it is worth noting that the basic formalization in Eq. is still very popular and widely used in practice (Verma et al.] 2024a Guidotti 2024h.
There exist numerous methods (mostly heuristics) Guuddoti 2024h for computing counterfactud explana- tions, ie., computing feasible solutions to Eq. [ Gradient- methods for solving Eq. 2 (Wachter et al.
2017], assuming diffcrentiable model, are extremely popular the literature (Guidotti 2024). For non-
differentiable models, such as tree-based models, evolutionary methods (Mothilal et al. 2020 Dandl et all, 2020) are commonly used. Furthermore, evolutionary methods also constitute the most popular choice in the case of categorical features, which often occur in real-world scenarios such as attrition business analyt- ics (Artelt & Gregoriades) 2023 2024). However, those existing methods usually compute a feasible solution only and are unable to guarantee optimality. In this context, a study of the computational complexity of the corresponding optimization problems being solved can provide insight into the cases in which it is (or is not) possible to (efficiently) compule optimal or approximately optimal counterfactual explanations.
It is important to note that Definition [ represents a non-causal approach, meaning it does not involve modeling underlying causal mechanisms. A separate branch of rescarch on counterfactuals exists that uses structural causal models to integrate causal knowledge (Karimi el al. 2020). However, in practice such causal models are often unknown and must be estimated from data or precisely defined with the assistance of domain experts. This work focuses solely on this non-causal approach because all of the litorature on the computational complexity of counterfactual explanations currently only considers the non-causal case.
As an alternative to Definition ! counterfactual explanations are also related the Minimum Change Required (MCR) considered in the computational complexity literature (Barceló et al., 2020). Here, the existence of a counterfactual det with an upper bound k on its cost ((6ct) is stated as decision problem:
Does there exist a da s.t. h(Zorig @ da) = yet and 0(0a) $ k?
(4)
Note that if the decision problem Eq. 4 is computationally hard, so is the corresponding optimization problem Eq. I (Brceló et al. 2020
In the context of plausible counterfactual explanations, Amir al. (2024) assumes the availability of an additional function (called contert indicator) Forig det + {0, 1) for distinguishing between plausible
3

---

Published in Transactions on Machine Learning Research (12/2025)
(I()) 1) and non-plausible (x(-) = 0) counterfactuals. This context indicator aT-) is the added
additional constraint to Eq. 4 to ensure plausible counterfactual explanations:
Does there exist a det s.t. h(torig @ det) = yet and π (atrig @ dct) and (( S k?
(5)
However, it is worth noting that apart from the plausibility formulation Eq. studied in (Amir et al. 2024 there exist numerous other plausibility formulations, such as causal plausibility (Karimi et al. 2023) that have not been considered so far when analyzing the computational complexity of computing counterfactual explanations.
2.1.1 Semi-factual Explanations
Semi-factual explanations (often just called semi-factuals) (Aryal & Keane 2023 Aryal 2024 Kenny & Huang, 2023), also known as "even if" explanations, highlight input changes that, unlike counterfactuals do and Y had been different, the outcome would remain unchanged", not alter the oulcome Le., "Even
These explanations provide a rationale for counterfactuals by illustrating which changes would not affect the outcome, helping users understand what modifications would leave the outcome intact. Compared counterfactuals, semi-factuals have received much less attention in the XAI community (Aryal & Keane
2023 The exisling research semi-factuals in XAI explores the explanation of reject oplions (Artelt & Hammer 2022), computational approaches for plausible semi-factual and counterfactuals (Knny & Keane 2021 1, as well as connecting semi-factuals and counterfactuals on a computational level (Aryal & Keane
2024
Unlike counterfactual explanations, there is no universally accepted formalization for semi-factual explana- tions. Formalizing semi-factual explanations requires balaneing two conflicting objectives (Aryal & Keane 2023 1) Maximizing the changes made to the inputs without altering the outcome, and 2) Minimiz- 2024
ing the number of changes to the inputs to facilitate casier human understanding. While some approaches look for sparse changes such that the distance to the decision boundary stays the same or becomes smaller (but not larger) (Artelt Hammer 2022 Kenny Keane 2021), another modeling approach refers to semiifactuals as minimum sufficient reasons (MSR) (Barceló et al. 2020; Ignatiev & Marques- 2021), also called Prime Implicant explanations, aiming to identify the smallest subsct of features that alone is sulficient for the observed outcome, i.e,, ignoring the values the other features Lake, the outcome will always be unchanged:
Does there exist an Ø&t s.b. (((aat)) = h (Zori)) and | S & and (dtar); = (Zorig)) Vi: (Wat); f1
(6)
where 1 denotes the default (turned off) value of a feature. Like in the case of counterfactual explana- tions Eq. Amir et al. (2024) extends Eq. 0 by additional context indicator Ezt {0, 1) for
dist iissisnugs between plausible (x(+) = 1) and non-plausible (r(-) 0) semi-factual explanations:
Does there exist an Vat s.t. h(xxr) = h((orrgg)
T (mxx)
|anatllo
(wat): (Worig) Vi: (æar), #1
Alternatively, Alfano et al. 2222 completely ignores the second objective and just maximizes the change such that the outcome remains unchanged:
Does there exist æar s.t. h((wa)) h(Zorig) and (KEorig, Fst) 2 k
(8)
where we abuse the previous notation and assume that ((..)) measures the distance distance/similartii siimiarity of two given instances. Note that Eq. assumes Sinary/categore features in order be meaningful (Alfano et al.) 2025)
and is also referred to as the Mazimum Change Allowed (MCA). Further note that only Eq. 6 and Eq. have been considered when studying the computational complexity of semi-factual explanations.
4

---

Published in Transactions on Machine Learning Research (12/2025)
2.2 Computational Complexity
In the following, we briefty introduce computational complexity and refer the interested reader to (Arora & Barak, 2009) for more details and formal definitions. There are different types of problems, and we will start by considering so-called decision problems where the objective is to compute a "yes" or "no" answer given some question on some input. As an example, Eq. shows a formal way of stating the MCR problem as a decision problem in which the informal version of the related counterfactual question is as follows: Is it possible to change the class outputted by a classifier by applying a small change to the input?
Regarding the relation of two (decision) problems, we say that a problem A is reducible to a problem B if we can solve problem A using a subroutine for solving B without spending too much time translating A into B. In this case, we will write A B since B, in a sense, is at least as hard to compute as A.
Computational complexity classes state how difficult it is to solve a given (decision) problem. In this context, we say that an algorithm (for solving a given problem) is a polynomial time algorithm if the execution time is polynomial in the size of the input. Some of the fundamental complexity classes for decision problems, as relevant for this work, are the following:
P (or PTIME)): The class P contains all decision problems where there exist polynomial time algorithm for computing the solution.
NP, coNP and DP: Informally speaking, a decision problem is in NP if there is an efficient procedure to prove that the answer is "yes" whenever this is the case. It is obvious that P S NP. It is an open problem whether * NP, but the general belief is that this is true (Arora & Barak] 2009). A problem B is said to be NP-hard if A S B holds for any problem A in NP. The relation - is transitive, so we can show that a problem C is NP-hard by showing B I C for a problem B known to be Na-hard. If we can show that a problem is NP-hard then it is unlikely that there is polynomial time algorithm for solving it since this would imply P NP. It is important to stress that a problem does not need to be a decision problem to be NP-hard. If a problem is NP-hard and a member of NP, we refer to the problem as being NP-complete. The coNP class contains the decision problems where "no" answers are efficiently verifiable. A decision problem is a member of the complexity class Dr if the answer for some input is "yes" if and only if the answer is "yes" for some problem A and "yes" for some problem B on the same input where A and B are members of NP and coNP, respectively.
D. Decision problems in 2> also allow a formal procedure for proving any "yes" decision, but proofs may take superpolynomial time. Analogously to NP, a problem in Σg can be Ed-complete, showing that the problem is at least as hard as any other problem in Mz. It is often conjectured that NP is a proper subset of 2.3
A second type of problems are counting problems, where the related question asks how many objects there are of a certain kind. As an example, let us revisit the MCR problem Eq. 4 for classifier taking binary input. A counting version of MCR could be formulated as follows: How many inputs within Hamming distance 5 from the actual input can change the output of the classifier? Note that this problem is at least as hard as deciding if such an input exists. The class #P for counting problems is the analogous class to NP for decision problems, and is unlikely that there is a polynomial time algorithm for solving a problem that is #P-complete since this would also imply P NP. Occasionally, the problem of enumerating objects of certain kind is considered for example, explanations for ML models instead of counting them.
The third and final type of problems that we consider in this work are optimization problems, where we focus on the subclass of minimization problems. Let us again consider the MCR problem Eq. A where a minimization version could be stated as follows: What is the closest input to the actual input for which the output of the classifier will change? Here we are trying to apply a minimum change to the input to change the output. In many cases, it is hard to find an exact solution to minimization problems, so we are looking for approximate solutions instead. An algorithm is a c-approzimation algorithm for a minimization problem if the algorithm is able to compute a solution with value of the objective that is not bigger than times the
5

---

Published in Transactions on Machine Learning Research (12/2025)
optimal value. With respect to the MCR example, this means that the change the algorithm recommends is within a factor from the minimum change required. A common technique (also applied in this work) for showing that a polynomial-ime algorithm for computing an approximate solution is unlikely is to show that the problem NP-hard. As noted above, the existence of such an algorithm would then imply P = NP, which is believed to be false.
2.3 Specific models considered in literature
Besides "classic" machine learning models such as decision trees, tree ensembles, multi-layer perceptrons (MLPs) (e.g., ReLU networks, i..,, MLPs with ReLU activation functions), perceptrons, k-ncarest neighbors (kNN), etc., the literature on computational complexity of counterfactuals also considers some "less popular" (but more general) models such as free binary decision diagrams and decision lists for Boolean functions. A free binary decision diagram (FBDD) is rooted directed acyelic graph encoding boolean decision function where the non-leaf nodes correspond to the binary variables and Icaf nodes encode the decision output (Barceló et al. 2020). Note that decision Irees (DT) are special instances of FBDDs where the graph is a tree. A Decision List (DL) constitutes an ordered list of IF-THEN rules whereby the condition statement is written as a logical conjunction over different features (Ignatiev & Marques-Sii Silva 2021
3 Overview of Computational Complexity Results
Existing work on the computational complexity of counterfactual and semi-factual explanations has studied a variety of different classifiers with special focus on perceptrons, ReLU networks, and FBDDs see Figure [ for overview.
3.1 Counterfactual Explanations
Most research on the computational complexity of counterfactuals considers classic counterfactuals (Defini- tion 1 without any additional constraints on plausibility, robustness, etc. Only very little work exists on robustness (w.r.t. model changes), plausibility, or global counterfactuals. We provide a summary of the complexity results, including two estraightforwadd implications from the literature (Corollaries [ and 2 in Table D Note that almost all existing work assumes discrete (i.e., binary) features, although some do not make any assumptions.
From Table 1 is becomes apparent that the computation of counterfactuals for ensembles of models is hard, and also for most single models, except monotonic classifiers and decision trees & diagrams. The effect of many additional properties, such as robustness to model changes and plausibility, on the compulational complexity remains unknown. However, it seems to be the case that adding plausibility constraints also makes the computation hard. Observing those "nogative" results raises the question of implications for the XAI community. In particular, how reasonable it is to aim for optimal explanations we elaborate on this further in Section 5
3.2 Semi-factual Explanations
Similar to the limited work on semi-factual explanations general, existing work on the computational
complexity of semi-factuals also limited compared to counterfactuals (see Table 1 Alfano et al. (2025)
explicitly studies the computational complexity of semi-factuals for few classifiers (following the maximum
change modeling approach Eq. B). However, most of the existing work (Bassan et. al. 2025 Marques-SS SSlva
ct al. 2021 Ignatiev & Marques-Siin Silva, 2021: Barceló et al. 2020 on the computational complexity of semi- factuals adopts the minimum sufficient reasons modeling approach Eq. 6 and states some complexity results, often as a byproduct of their study of counterfactual explanations. We provide a summary of the complexity results in Table 2 Note that in contrast. to counterfactual explanations (see Table D the problem of
TTe stated complexity classes in this table assume the worst-cuse of ReLU uetwork for implementing the context indicator
TT-) complexitics for other functions can be found in Amir et 2024
For 2 and the norm for the norm the complexity TIME Barceló et
2025 For discrete (binary) domain
it always NP-complete [Barceló al. 2025)
6

---

Published in Transactions on Machine Learning Research (12/2025)
F10255
ReLU Net
20225
FBDD
Dazaan 2005
Ensembles
Perceptron
2002
Randon Forest
Looe Ac Marretea- S0l Silo
Trees
Additive Trees
Chn 2016
ReLU Net
201 8
al
Wiug Allans
10:20
2024
Perceptron
Amnr
A Blano
Classifier Type
DL
Single
3024
Lenattine de
GNN Komnn
Vorma oe mt
Any Monotonic
Trees
DT
LOOL us mi..
Mar
Hnvontto al BEES
Baroalo et ml 2022
kNN
8024
FEDD
Kodi ST
Figure 1: Overview of the classifier types for which the computational complexity of counterfactuals and/or serni-factulls has been studied in the literature.

---

Published in Transactions on Machine Learning Research (12/2025)
Types of Counterfuctuals
Classifiers
Classic (Single)
Classic (Enumerate)
Robustes
Plausiblem,
Global
NP-hard
Any
Hadrigues
PTIME
XP-complete
Monotonic
Marques- Silva et
2091
2021. Marques-Silve Silve. al
NP-complete
N
2
Barcotd at al.
9025
Single
GNN
NP-complete
NP-hard
2024
PTIME
NP-complete
Perceptron
2024
NP-complete
NP-hard
NP-complete
ReLU Net
Bareatd et al. 9020
Marzari en at. 2024
Amir as at.
2024
PTIME
PTIME
DT
Trees
2091
PTIME
NP-complete
FBDD
NP-complete
Perceptron
Ensembles
Barzan
NP-complets lete
NP-hard
NP-complete
ReLU Net
Razzan at 8025
Corollary
Coreilary
NP. hard
Additive Trees
Trees
Oui
NP-complet
FBDD
Table 1: Computational complexity of counterfactual explanations.

---

Published in Transactions on Machine Learning Research (12/2025)
Modeling of Semi-factuals
Minimum Sufficient Reason (Ba
Maximum Change Allowedar Classic
Classifiers
Classic
Plausible
PTIME
Monotonic
Marcquss-Blee
22023
NP-hard
kNN
Barceld at al 2025
PTIME
D complet
PTIME Alfano
Perceptron
Single
2024
--oomllete
NP PP-complete
ReLU network
Barcels
PTIME
Extended Linear
Marquea-SBie Stlva
2020
PTIME
DT
Isen
2020
Trees
NP-hard
DL
Marques- Silva
XP-complete
D compleee
PTIME
FBDD
Barcels
2020
Amir al 2025
Alfano 2025
2
compleete
Perceptron
Basonn et sl.
2025
Ensembles
2 --complete
ReLU network
T 2 -complete
FBDD
Basena al.
2025
Dl-complete
Random Forest
Ieea & MarqquesSSilv 2021
Table 2: Computational complexity of semi-factua explanations.

---

Published in Transactions on Machine Learning Research (12/2025)
enumerating all possible semi-factual explanations has not been studied in the literature. Only Marques Silva et al. (2021) proves that enumerating all possible MSRs (Fq. 6 with polynomial-time delay is NP-coepeeee. Similar to the case of counterfactual explanations (see Section 3.1), Table 2 shows that the computation of
semi-factuals for almost all models (except linear models and decision trees) is computationally hard.
4 New Inapproximability Results for Counterfactual Explanations
We identify a gap in the literature regarding the inapprozimability of counterfactual and semi-factual expla- nations, as most of the literature considers only their exact computation. An exception is a result by [Wnng ct al. (2018) showing that, unless NP = P, no polynomial time (1 (1)) In n-aproxximatio algorithm exists for the MCR problem (Eq. [ with 0(.) = (.) for ReLU networks where n is the number of neurons. This means that any polynomial time algorithm for computing the closest input that will change the output can face sccnario where the computed counterfactual is at distance at least In times the optimal (roughly).
Focusing on counterfactual explanations, we extend this area by introducing new inapproximability results for ReLU neural networks, additive tree models and kNN models, Before detailing the inapproximability results, we revisit the counterfactual explanation problem as defined by Wachter et al. (2017). We refer to the optimization problem defined in Remark as WACHTER CFE and define its input and output as follows.
Definition 2 (WACHTER-CFE problem). For a given regressor h(,), on instance Borig, and a requested predicttion Yef. the computation of a counterfactual explanation of the prediction h(Worig) is phrased as the following optimization problem (equivalent to Eq. 2)
arg arg min ( 2 6e), Hes) + X -((x))
(9)
where X > O denotes a user-specified hyperparameter for balancing between obtaining the requested prediction Vef and minimizing the costcoompeziig of the counterfactual def-
The final counterfactual sample aaf is oblained by applying the counterfactual det to the original inslance Dorig: Def Zorig e def.
Note that we extend the notion of h(-) as a classifier to the more general notion of a regressor. Since classifi- cation is a special case of regression, Definition2 covers a larger spectrum of applications. Furthermore, Eq. 9 from Definition 2 can be reduced to the MCR formulation Eq. 4 by setting À to a sufficiently small positive number recovering the constrained optimization problem where the cost (i.e., amount of change) has to be minimized subject to the correctness of the counterfactual 8a. Thercfore, our study of WACHTER-CFE (Definition
2 allows us to make more general statements, implicitly including the MCR formulation Eq. 4 The inputs Torig are discrete/ categorical inputs, for example, modeling yes no features. While we could compute an exact solution to the WACHTER-CFE problem (Definition 2), we have already shown that this is known to be difficult in a variety of settings. Thus, an alternative would be to compute an approximate solution, i.e., building an efficient algorithm guaranteeing solution with a value of the objective within some factor K of the optimal value for some K close to
In the following, we investigate the computational complexity of such approximation algorithms for the WACHTER-CFE problem (Definition 2 and prove that such algorithms do not exist for classic regressors with discrete input, even if K is exponential in the size of the regressors. For any polynomial p(n). we show that there is no polynomial time algorithm for the WACHTER-CTE problem (Definition 2 with approximation factor 2P(n) even for simple neural networks, additive tree models and kNN models with discrete input under the assumption P + NP (n refers to the size of the regressors, such as the number of neurons or number of nodes). More precisely, let det be the optimal value according to Definition 2 The presented theorems state that there does not exist any polynomia--time algorithm that is guaranteed to
The stated complexity classes in this table assume the worst-cuse of ReLU uetwork for implementing the context indicator T(); complexitics for other functious can be found in Amir al. 2
4 'oor 2 and continuous discrete (binary) domain not matter which norm is used. 5he exact value depends on the specific problem and its parameters, such as the upper bound from Eq.
10

---

Published in Transactions on Machine Learning Research (12/2025)
compute solution de' to Definition 2 such that:
[hh(aorgg @ det (e()) yet) + A 0(6,t) s 2p(m) 22pl)) (e(h(aorig @ det), Met) + 0(6.))
(10)
This means that computing approximately optimal counterfactuals also computationally hard, and we can not hope to find an efficient (i.e., polynomial-time) approximation algorithm computing a der satisfy- ing Eq. I0
The presented thcorems hold for regressors h(.) taking binary input, i.c., X' = {0. 1] it is usually assumed in the literature on computational complexity of counterfactual explanations (Amir et al. 2024). features in applications, such as attrition and business analytics (Artelt & Gregoriades) 2023 2024). Therefore, our presented theorems directly apply to important real-world scenarios and provide insights into how well optimal counterfactual explanations can be approximated in such scenarios. The loss E(-) the squared error, and the cost 0(-) of the counterfactual is a function satisfying max, ((z) S q(n) for some polynomial g(-). As an example, the loss 0(-) could be the 1-norm for the binary vector det, and the operator @ could be the xor operator, implying that we try to minimize the number of bits to flip in the input to get a good outpul from the regressor. The proofs of our results can be found in Appendix A.2 and are based on a 3-SAT reduction, which constitutes a common proof strategy for proving NP-completeness of a problem (Arora & Barak 2009) and have also been used in some work on computational complexity of counterfactuals (Marzari et al. 2024). The formal statements of the theorems as follows:
Note that practitioners often face discrete or binary/categorta
Theorem If P4NP, then the following holds for any polynomial p(n):
There is no polynomial time approszaanai algorithm for the WACHTER-CFE problem (Definition for neural networks (ReLU) with nodes and one hidden layer.
For additive tree models, will restrict our attention to forests consisting of binary decision trees where the aggregated response is the average of all the outputs of the trees.
Theorem 2. If P4NP, then the following holds for any polynomial p(n): There is no polynomial time 20(") caproroaitiii algorithm for the WACHTER-CFE problem (Definition for additive tree models with total of nodes.
Finally, have theorem for kNN models:
Theorem 3. If PVNP, then the following holds for any polynomial p(n): There is no polynomial time -aprrrzaaitiii algoritlum for the WACHTER-CFE, problem (Definition for kNN models of size n.
5 Discussion of Open Questions & Implications for the XAI Community
Computational complexity analysis provides a critical view of the difficulty of computing various types of counterfactual and semi-factual explanations. This analysis can help users of XAI methods towards models that best suit the kinds of explanations they require. We now discuss the wider implications of computational complexity analysis, in the hopes of spurring more interest within the XAI community to analyze the complexity of existing and new methods.
We propose that computational complexity should be taken into consideration when proposing new expla- nation methods. While a new explanation type/fore sype/formalizatin might. have some appealing properties, is also important to make sure that those explanations can be computed efficiently. Furthermore, it ought be clearly understood which parameters (e.g., dimensionality, model-size, etc.) constitute the computational bottleneck.
As highlighted in this work, many counterfactual and semi-factual explanations are "hard" to compute. This might question their usefulness. That is, we must ask whether it makes sense to ask for such explanations if they are hard/complete to compute, and also difficult to approximate. We argue that it might be reasonable to move away from the idea of computing the "best" (i.c., closest or optimal) counterfactual/see factual, and instead aim for some counterfactual/ sestttallssmm-ffctttte factual with reasonable properties such that still remains useful in practice. Indeed, existing work on computing munnterfachual/semiifaea explanations
11

---

Published in Transactions on Machine Learning Research (12/2025)
often utilizes heuristics that end up in local minima, yet those explanations often turn out to be useful (Smyth & Keane] (022). In this context, propose that future work should focus more on average-case performance analysis, as well as on less strict formulations that allow non-optimal solutions, such as Defimition 2 This would better align with practice and bridge the gap between thcoretical worst-case analyses and the scenarios in the real world.
Computational complexity analysis usually assumes categorical imput features Amir et al. (2024) Although categorical features occur quite often in real-world scenarios, such as attrition and business analytics (Artelt
& Gregoriades 2023 2024 there also exist scenarios with continuous features. In this context, the presented findings and complexity results do provide valuable insights for many real-world scenarios involving categor- ical features. In particular, they state that in those scenarios, even with popular state-of-the-art methods such as evolutionary methods (e.g, DiCE) (Mothilal et al. 2020 Dandl et al. 2020). we can not expect to get an optimal counterfactual/semmi-fea factual explanation or even a "good" approximation. However, the presented findings do not provide statements for cases with contintous features, leaving them as largely unexplored area from a computational complexity perspective. Existing work on continuous features often proves optimality by proving convexity of the optimization problem to be solved using convex approxi- mations to prove approximate optimality (Artelt & Hammer 2020 However, formal statements for general non-convex scenarios remain an open problem, with the consequence that for many gradient- braseent-based methods, it remains unclear how optimal the generated explanations are.
A major question is whether it is acceptable to use classifiers rrefeessorrrr for which the computation of (certain) explanations is "infeasible". We argue that this likely depends on the application domain and the importance wwwterrfaattaassmm-faaaaatt
of "optimal/best"
explanations. While in some applications a sufficiently good explanation will suffice (as discussed in the previous paragraph), other applications might require exact ones, with the consequence that not every classifier type can be used, given the computational hardness of computing such exact/ estet/optimal counterfactual/ htt////mmiifttuse explanations. In this context, our comprehensive wtwprrffattttussmmssfeeeeeeeeeee can
overview of the computational complexity for different types of models and /ammaaiailaaaaaaaaaaa explanations help decision makers in deciding whether is appropriate to use counterfactuall in particular application or not.
6 Conclusion
This work addressed the computational complexity of generating explanations for variety of models and types of counter/semi-facee remain many open questions and thus opportunities for advancing current. knowledge about the complexily of different explanations. We observed that in many settings, the computation of counterfactual and semi- factual explanations is computationally hard. We extended those findings further by showing that we cannot even efficiently compute counterfactuals with an exponential approximation factor.
explanations. Our overview of the current stato-of-tho-art shows that there
Most existing work on explanations considers "plain" counterfactual and semi-factual explanations, which are known to black other important properties such plausibility, robustness, etc. More rescarch on the complexity of these extended definitions is needed, as outlined in the missing entries in Tables [ and 2 In this context, it is worth noting that there exist numerous different formulations of robustness and plausibility, leaving large field open for future research. Furthermore, the absence of any complexity results on causal counterfactual explanations is alarming given the fact that counterfactuals are often deployed in the real world, where actionability and causality are key requirements.
We acknowledge an important limitation of our work, namely that just because a particular type of expla- nation is shown to be computationally difficult, this does not mean that these types of explanations are useless or impractical in practice. Heuristic or approximation methods could be used in place of optimal approaches, but the compatibility of these methods with industrial requirements and regulatory schemes must be carefully considered. For future work, investigating the quality of heuristic and approximation schemes from a formal perspective could provide critical guidance for industry and governments for using and regulating XAI systems. In this context, there is also an urgent neod for formal statements on the optimality of existing and commonly used heuristic and approximation methods for cases with continuous features, given that those cases have been mostly ignored in computational complexity analysis so far. It.
12

---

Published in Transactions on Machine Learning Research (12/2025)
would also be interesting to move away from worse-case analyses, towards average-case analyses, considering the WACHTER-CFE formulation instead of the strict MCR formulation for allowing non-oplimal solutions, as is usually done in practice. Finally, the limited work on semi-factual explanations (compared to counter- factual explanations) is alarming and needs more attention from the community. Not only concerning their computational complexity, but also in general, such as evaluation methods, comparison of different formal- ization and modeling approaches, as well as algorithms for efficiently computing semi-factual explanations. In particular, there an urgent need for (in-)approximabblity studies of semi-factuals, similar what we did in Section A However, their difference from counterfactual explanations, in particular the absence of the contrasting property, hinders the transferability of existing results for counterfactuals to semi-factuals.
Acknowledgments
This research was supported by the Ministry of Culture and Science NRW (Germany) as part of the Lamarr Fellow Network. This publication reflects the views of the authors only.
References
Gianvincenzo Alfano, Sergio Greco, Domenico Mandaglio, Francesco Parisi, Reza Shahbazian, and Irina Trubitsyna. Even-if explanations: Formal foundations, priorities and complexity. Proceedings of the AAAI
Conference on Artificial Intelligence, 39(15):15477-15555 Apr. 2025. doi: 10.1609 14669/aaai.vaa /aaiaaaaaaaaaaaaaa/a v39115.33684.
URL https://ojs. http::////ss.aaa.oooooo awai. www.rr/n//g...o..e wwtpg//ndx...pp//AAA.... http:p//AAAAA/tattrae///////////
Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In- Distribution Model Interpretation. arXiv preprint arXiv:2408.0300 2024. doi: 10.48550//cXivv2240.. 03915. URL https://doi. 48t///0..455//rr///
2408.03911
Sanjeev Arora and Boaz Barak. Computational Complezity: A Modern Approach. Cambridge University Press, USA, 1st edition, 2009. ISBN 0521424267.
André Artelt and Andreas Gregoriades. 'how to make them stay?': Diverse counterfactual explanations of employee attrition. In Proceedings of the 25th International Conference on Enterprise Information Systems, ICEIS 2023, Volume 1, Progue, Czech Republic, pp. 532 538. SCITEPRESS, 2023. doi: 10. 5220 0000000011111000444... URL https:://oi..... /ttg//0..220/01111100003022
André Artelt and Barbara Hammer. Convex Density Constraints for Computing Plausible Counterfac- tual Explanations. In Igor Farkaš, Paolo Masulli, and Stefan Wermter (eds.), Artificial Neural Net- works and Machine Learning ICANN 2020, pp. 353 365, Cham, 2020. Springer International Publish- ing. ISBN -61-6-0000-1600-00
doi: 000709978--00-00
28. URL lattps://dat http:///...ogg11110000010 org/10.
978- 078-3-030-61609-0 28
André Artelt and Barbara Hammer. "Even if.. .E...".. " "-Diverse Semifactual Explanations of Reject. In 2022 JEEE Symposium Series on Computational Intelligence (SSCT), pp. 854-859. IEEE, 2022. doi: 10.1109/
0C0E51003.22222.10022133 URL https://ddii htt/////...orrr..../////////////
2022. 10022199
André Artelt and Barbara Hammer. "Explain it in the Same Way!" Model-Agnostic Group Fairness of Counterfactual Explanations. In Amir Ofra, Tim Miller, and Hendrik Baier (eds.), Workshop on XAI, 2023. URL https://sites. google. com/viex/xai2222 xxi2023
André Artelt, Valerie Vaquet, Riza Velioglu, Fabian Hinder, Johannes Brinkrolf, Malte Schilling, and Bar- bara Hammer. Evaluating Robustness of Counterfactual Explanations. In IEEE Symposium Series on Computational Intelligence, SSCI 2021, Orlando, FL, USA, December 5-7, 2021, pp. 1-9. IEEE, 2021. 2021 2666996008888
doi: 10.1109/SSC1004111222.60000 URL http::///ooo..oggg.0000000//////
André Artelt and Andreas Gregoriades. Supporting organizational decisions on how to improve customer repurchase using multi-instance counterfactual explanations. Decision Support Systems, pp. 114249, 2024. ISSN 0167-9236. doi: 10. 10.1016/j.dss.224.111
URL httpp:://ww. httpp://www.cceenediieee..... htt.:///ddrrettt..oooo//ccccceee
13

---

Published in Transactions on Machine Learning Research (12/2025)
Saugat Aryal. Semi-factual Explanations in AL In Proceedings of the AAAI Conference on Artificial In- telligence, volume 38, pp. view/30390
2024. URL htR..https:/// https://ojss. www.:aaaaaaaaa.aaaaaaeeae.ee.eae /ptpp////a////rccclcl////////
Saugat Aryal and Mark T Keane. Even if explanations: Prior work, desiderata & benchmarks for semi- factual xai. arXiv preprint 1111:2301.111900, 2023. doi: 200.5000//X...211111199 URL https://doi. org/ 10. 48.50/ arrivv 2301 11970
Saugat Aryal and Mark T Keanc. Even-Ifs from If-Onlys: Are the Best Semi-factual Explanations Found Using Counterfactuals as Guides? In International Conference on Case- Based Reasoning,
pp- 33-49 Springer, 2024. doi: 10.1007/978-3-031-684666 3. URL htttps//doi.orgg::
Pablo Barceló, Mikaël Monet, Jorge Pérez, and Bernardo Subercaseaux. Model Interpretability through the lens of Computational Complexity. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15487-15498. Cur- ran Associates, Inc., 2020. URL
Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth, Bernardo Subercaseaux, and José Ver- schae. Explaining k-nearest neighbors: Abductive and counterfactual explanations. arv preprinl orXiv:250L.06076 2025. URL https::/ddii. /tw.:////////////////////// www.v..511.060000 2501.06074
Shahaf Bassan, Guy Amir, Meirav Zehavi, and Guy Katz. On the (un) interpretability of Ensembles: A Computational Analysis, 2025. URL
Ruth M. J. Byrne. Counterfactuals in Explainable Artificial Intelligence (XAI): Evidence from Human Reasoning. In Sarit. Kraus (ed.), Proceedings of the Evvety-Fiighte International Joint Conference Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. 6276 6282, 2019. doi: 10. 2019/876
24963 (1///////CAA.21////5// /866. URL https: h/ta:://dooo http://doo.oo/////// 10. 24963/ijcai /01.:/a........666666
Zhicheng Cui, Wenlin Chen, Yujie He, and Yixin Chen. Optimal Action Extraction for Random Forests and Boosted Trees. Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discov- and Data Mining, 2013. doi: 10. 10.1145/2783355827882222 URL https://doi wrg/10../........ 115///2231145/288225588 2783281
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual expla- nations, 2020. URL http:://xxddo/ doi. org/10.
European Parliament and Council of the European Union. Regulation (eu) 2024/1689 of the european parliament and of the council of 13 june 2024 laying down harmonised rules on artificial intelligence and amending regulations (ec) no 300/2008, (eu) no 167/2013, (eu) no 168/2013, (eu) 2018/858, (eu) 2018/1139 and (eu) 2019/2144 and directives 2014/90/en (eu) 2016/797 and (eu) 2020/ 1828 (artificial intelligence act), June 2024. URL 3A32024R1689
www.pa. wttp/eglllcoteee///////aaaaeaaa/ ?uri=CEEXY/
Accessed: 2025-05-02.
Michael R. Garey and David Johnson. Computers and Intraclabilily; Guide the Theory of NP- Completeness. W. H. Freeman & Co., USA, 1990. ISBN 0716710455.
Riccardo Guidotti. Counterfactual explanations and how to find them: literature review and benchmarking, Data Min. Knowl. Discor,, 38755) 2824, 2024. doi: 1140077/110618002--0038003 URL URLhttts::///// h/ttp::///o..
0rz/100.107//81061--0222-00
Xuanxiang Huang, Yacine Izza, Alexcy Ignaticv, and Joao Marques-Silva. On efficiently explaining graph- based classifiers. In 18th International Conference on Principles of Knowledge Representation and Rea- soning (KR 2021), 2021. doi: 2..24963KKR.202 /34. URL https://::///i:. wtw.oiiorgg/11.. .0211/4
14

---

Published in Transactions on Machine Learning Research (12/2025)
Alexey Ignatiey and Joao Marques-Silva. SAT-based rigorous explanations for decision lists. In Theory and Applications of Sulisfiabillly SAT 2021: 24th International Conference, Barcelona, Spain, July 5-9, 2021, Proceedings 24, pp. 251 269. Springer, 2021. doi: 10. 10.1007/978-3-1 000------0--022----- 18. URL httpss///ini httpss//ink.ssprnggrr.oom springer.
3_18
Yacine Izza and Joao Marques-Silva. On explaining random forests with sat. In 30th International Joint Conference on Artificial Intelligence (IJCAI 2021). International Joint Conferences Artifical Intelligence (IJCAT), 2021. doi: 10.24963 2224966/1JCAT.2222 /356. URI. lnttps://doi.org// http://....rr/110222222///////// 2021/356
Yacine Izna, Alexey Ignatiev, and João Marques-Silva. On explaining decision trees. CoRR, 22000. 2020. URL
Amir-Hosscin Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Modcl-agnostic counterfactual expla- nations for consequential decisions. In International Conference on Artificial Intelligence and Statistics, pp. 895-905. PMLR, 2020. URL https::/prooceeddngg mlr wttp://www........s///so/o//o///
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A Survey of Algorithmii Recourse: Contrastive Explanations and Consequential Recommendations. ACM Comput. Surv., 55(5): doi: 10.1145/3527844 URL htttps://oi.
95:1-95:29, 2023.
1145/3527848
Eoin Kenny and Weipeng Huang. The utility of "even if" semifactual explanation to op- timise positive outcomes.
Advances in Neural Information Processing Systems, 36:52907- URL https://proceedinng.. mewpeeerdddinnnnnnn..ses..e. neurips www.:/wwwu..ppppppeeeeeeee wc/paper.p.p... httpl/appprrlleeelllalllle #ilees/aperr/222/ hash//
52935,
2023.
abe
Eoin M Kenny and Mark Keane. On generating plausible counterfactual and semi-factual explanations for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11575 11585, 2021. doi: 10.1609 htt.//aaa.....1..... view/17377
v35i13. 17377. URL https://ojs aaaai.org/inng php/ AAAI/article/
Mert Kosan, Zexi Huang, Sourav Medya, Sayan Ranu, and Ambuj Singh. GCFFxplainer: Global Counter- factual Explainer for Graph Neural Networks. ACM Transactions on Intelligent Systems and Technology, 2024. doi: 10.1145/3698108. URL https://dl. acm. www..o////////////////e/e// 1145/3698108
Francesco Leofante and Nico Potyka. Promoting Counterfactual Robustness through Diversity. pp. 21322 21330, 2024. doi: 10.1609 AAAA V38119.0112, URL
ww8.19...1.0. 30127
Francesco Leolante and Matthew Wicker. Robust Explainable AT. Springer Nature Switzerland, 2025. doi: 10.10077978-33001-890222 URL http://xx doi 00g/110..007//7888300----8222220
João Marques-Silva, Thomas Gerspacher, Martin C. Cooper, Alexey Ignatiev, and Nina Narodytska, Ex- plaining naive bayes and other linear classifiers with polynomial time and delay. In Hugo Larochelle, Marc'A Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neu- ral Information Processing Systems 33: Anreual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6- 2020, virtual, 2020. URL Abstract.
paper/2020//ea hwspe///hash/eeeee http:///hhhhaacaaaaaaa22222////0
Joao Marques-Silva, Thomas Gerspacher, Martin C Cooper, Alexey Ignatiev, and Nina Narodytska. Ex- planations for Monotonic Classifiers. In International Conference on Machine Learning, pp. 7469-7479, PMLR, 2021. URL httpps://proceeiingg mlr. press/
wwtppp/sssseeeeeeeeepeepeepp h/////1319/// wttp://mrruuussssssssaeeee html
Luca Marzari, Francesco Leofante, Ferdinando Cicalese, and Alessandro Farinelli. Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations. In Ulle Endriss, Francisco S. Mclo, Kerstin Bach,
Alberto José Bugarín Diz, Jose Maria Alonso-Moral, Senén Barro, and Fredrik Heintz (eds.), ECAI 2024
-7th European Conference on Artificial Intelligence, 19-24 October 2024, Santiago de Compostela, Spain -Including 13th Conference on Prestigious Applications of Intelligent Systems (PATS 2024), volume 392 of Frontiers in Artificial Intelligence and Applications, pp. 1059-1066. IOS Press, 2024. doi: 10.3233/ FATA240597. URL https: ://ooi. .eeillorg//// 1033//2/////AA4405577
15

---

Published in Transactions on Machine Learning Research (12/2025)
Dang Minh, H. Xiang Wang, Y. Fen Li, and Tan N. Nguyen. Explainable artificial intelligence:
comprehensive review. Artificial Intelligence Review, 35:5333533 3568, November 2021. doi: 10.1007/
000462-021-10088-- URL http://dx. doi.ddoi.. owg/10. 1007/ 0201-4400-02-1---7
Christoph Molnar. Interpretable Machine Learning. 2019.
URL https:///chrsstophm..
1o/
Ramaravind Kommiya Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Mireille Hildebrandt, Carlos Castillo, L. Elisa Celis, Salvatore Ruggieri, Linnet Taylor, and Gabriela Monfi--Frttuaa (eds.). FAT* '20: Conference on Fairness, Accoumlabiliil, and Transparency, Barcelona, Spain, January 27-30, 2020, pp. 607-617. ACM, 2020. doi: 10.1145/3851005.33777 3372800 URL /tttpp://doi.orre 1111//0..11153311999190 3372850
Maja Nisevic, Arno Cuypers, and Jan De Bruyne. Explainable AI: Can the AI Act and the GDPR go out for a date? pp. 1-8. IEEE, June 2024. doi: 00110///jen60099.00000 1064.966999944 URL http://dx.de doi.
org/10. 10. 111.//900CGG00999 2024. 10649994
Rafael Poyiadzi, Kacper Sokol, Raúl Santos-Rodriguu Tijl De Bie, and Peter A. Flach. FACE: feasible and actionable counterfactual explanations. In Annette N. Markham, Julia Powles, Toby Walsh, and Anne T.. Washington (eds.), ATES '20: AAAT/ACM Conference on AT, Ethics, and Sociely, New York, NY, USA, February 7-8, 2020, pp. 344 350. ACM, 2020. doi: 10.1145/3375522733375555 //doi.org//i 1145/ 3375850
URL https:
Maria Riveiro and Serge Thill. The challenges of providing explanations of AI systems when they do not behave like users expect. In Alejandro Bellogin, Ludovico Boratto, Olga C. Santos, Liliana Ardissono, and Bart P. Knijnenburg (eds.), UMAP '22: 30th ACM Conference on User Modeling, Adaplation and Personalization, Barcelona, Spain, July 4 7, 2022, pp. 110 120. ACM, 2022. URL attpps://oi... org/
10. 111114/3533222333111111
Wojeiceh Samek and Klaus-Rober Miller. Towards explainable artificial intelligence. pp. 5-22. Springer International Publishing, 2019. doi: 10.1007 07177/997770-0-28----8 1. URL http::/dx..oo /007
Shubham Sharma, Jette Henderson, and Joydeep Ghosh. CERTIFAI: A common framework to provide explanations and analyse the fairness and robustness of black-box models. In Annette N. Markham, Julia Powles, Toby Walsh, and Anne L. Washington (eds.), AIES '20: AAAI/ACM Conference on AI, Ethics, and Society, New York, NY, USA, February 7-8, 2020, pp. 166-172. ACM, 2020. doi: 10.1145/337562 3375812. URL /attps://doi wtt.:....../////....111 1145/3375627 3375812
Shubham Sharma, Alan H. Gee, David Paydarfar, and Joydeep Ghosh. FaiR-N: Fair and Robust Neural Networks for Structured Data. In Marion Fourcade, Benjamii Kuipers, Seth Lazar, and Deirdre K. Mulligan (eds.), AIES '21: AAAI/ACM Conference on AI, Ethics, and Society, Virtual Event, USA, May 19-21, 2021, pp. 946-955. ACM, 2021. doi: 10.1145/3461702.4465555 URL httpp:://ai.orr::: 3461702.346255
Barry Smyth and Mark T Keane. few good counterfactuals: generating interpretable, plausible and diverse counterfactual explanations. pp. 18 18-32, 2022. doi: 10.1007/978:33-81-144222 2. URL https
Stratis Tsirtsis and Manuel Gomez Rodriguez. Decisions, counterfactual explanations and strategic behavior. Advances in Neural Information Processing Systems, 33:16749 16760, 2020. URL http::/t///pr.
aww.:/tattaa-bbataattc.a.aaaaac. .html
Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by prototypes. pp. 650 665, 2021.
Sahil Verma, Varich Boonsanong, Minh Hoang, Keegan Hines, John Dickerson, and Chirag Shah. Coun- terfactual Explanations and Algorithmic Recourses for Machine Learning: A Review, 2024a. URL http://///bi.oorg1..111...3.
16

---

Published in Transactions on Machine Learning Research (12/2025)
Samidha Verma, Burouj Armgaan, Sourav Medya, and Sayan Ranu. InduCE: Inductive counterfactual
explanations for graph neural networks. Transactions on Machine Learning Research, 2024b. URL. https:
Julius von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the Fairness of Causal Algorithmic Recourse. In Thirly-Siath AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty- Fourth Conference Innovative Applications of Artificial Intellignnce, TAAT 2022, The Twelveth, Symposium on Educational Advances in Artificial Intelligence, EAAT 2022 Virtual Event, February 22 March 1, 2022, pp. 9584 9594. AAAI Press, 2022. doi: 10.1609/AM AAAI. V3619.21199 URL hattps:///al http:///ooo..r///....o 1609/ ww619.v......... 21199
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without open- ing the black box: Automated decisions and the GDPR. Harv. JL & Tech., 31:841, 2017. URL https://heinnnnling httg:HooLPPageeaaddde-ttee httpa//aeeec.a..oooooaa/aaaaaaaa sent=111 casa pooloooiiooccccocoooooooooo
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Danicl, Duane Boning, and In- derjit Dhillon. Towards fast computation of certified robustness for ReLU networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, vol- une 80 of Proceedings of Machine Learning Research, pp. 5276 5285. PMLR, 10 15 Jul 2018. URL
https::/proceediing mlr, Trress/880/weng11e html
Songming Zhang, Xiaofeng Chen, Shiping Wen, and Zhongshan Li. Density-based reliable and robust ex- plainer for counterfactual explanation. Expert Syst. Appl., 226:120214, 2023. doi: 10.1016/J.ESWA 120214. URL httph: http::://l...rr//100000000 eswa. 2023. 120214
A Appendix
A.1 Counterfactual Explanations
A.1.1 Ensembles of ReLU Networks
Corollary 1. The computation of robust counterfactual erplanations (as defined in Marzari et al. (202/) for an ensemble of ReLU networks is NP-hord.
Proof. An ensemble of MLPs can be written as a single MLP in particular for ReLU networks. Conse- quently, the statement follows from (Marzari et al. 2024
Corollary 2. The compulation of plausible counterfuctual explunations (as defined in Amir el al. 2024 for an ensemble of ReLU networks is NP-complete.
Proof. An ensemble of MLPs can be written a single MLP in particular for ReLU networks. Conse- quently, the statement follows from Amir et al. 2024).
A.2 Proofs of Theorem and 3
For our three proofs, we will use a reduction from the famous 3-SAT problem that is NP-complete (Garey & Johnson 1990). Note that reductions from 3-SAT constitute a popular proof strategy for proving NP- completeness of a problem (Arora & Barak 2009). In the context, of the complexity analysis of counter- factuals and semi-factual explanations, reductions to existing problems constitute the most popular proof stralegy. In particular, reductions from 3-SAT (Marzari el. al. 2022). SAT (Ignatiev & Marques-Silval 2021 vertex cover (Barceló et al. 2025), and Knapsack (Alfano et al.) 2025). In our case, we aim for a reduction from 3-SAT bocause it aligus well with the contrasting property of counterfactuals and has been successfully used before as a proof strategy (Marzari et al. (024).. The input to the 3-SAT problem a Boolean formula in conjunctive normal form (CNF) with clauses consisting of no than three literals. The objective is
17

---

Published in Transactions on Machine Learning Research (12/2025)
M
M
M
Bias:
Bias: -
C1
61
b2
100
T1
2
X2
33
T3
Figure 2: A neural network with hidden layer used the regressor h(-) in the reduction from the 3-SAT problem to the WACHTER-CFE problem (Definition 2). The clause mXy æ2 V mag is clause in the CNF formula defining the 3-SAT instance. Connections with no weight shown in the figure have weight 1.
decide whether the Boolean formula is satisfiable. Actually, we are using restricted version of 3-SAT where each clause contains exactly three distinct literals. There is straightforward, well-known reduction showing that the restricted version is NP-complete as well.
Proof of Theorems 7 As mentioned earlier, we will use reduction from the restricted 3-SAT problem. The intuition behind the proof is to turn an instance of 3-SAT into WACHTER-CFE instance (Definition 2 with a regressor that outputs either 0 or a very big number M where 0 corresponds to yes-instances of 3-SAT. If we efficiently can solve the WACHTER CFE problem (Definition 2 approximately with target yet = 0, then we also can solve 3-SAT efficiently, which is contradiction. Now, assume that there polynomial time appr-xpproiniaiion algorithm A()) for the WACHTER-CHE problem (Definition 2
An instance of the 3-SAT problem is transformed into the MACHTER-CFF instance (h, Torig Wlff A) where h(-) the neural network with one hidden layer shown in Fig. with M = Vmax, 0(z) 2p(m) and Corig = 0, Met 0, 1. The regressor h(-) has an input neuron for each literal encoded according to the boolean value of the corresponding Boolean variable. For each clause, there is neuron in the hidden layer that will have output 0 if the clause is satisfied and M otherwise. There is also neuron in the hidden layer for each Boolean variable that outputs M if both the neurons for the literals for that variable in the input layer is and 0 otherwise.
The number of nodes n the regressor h(.)) is polynomial the size of the 3-SAT instance, and log M is polynomial in n. This leads the following observation:
Observation 1. The WACHTER-CHD inslance con be buill in polynomial lime.
Another key observation is the following, which is not difficult to prove:
Observation 2.
The oulpul of the regressor h(.)) is either O or al least M. If x: is a veclor corresponding to a satisfying assignment of the Boolean variables for the 3-SAT instance, then h(x) = 0. If h(x)) = 0, then we can construct satisfying assignment of the Boolean variables for the 3-SAT instance from æ.
Let w.t A(h, Forig, yet, X) be the output of the approximation algorithm A(-) for computing counterfactual explanation. Now, assume that the 3-SAT instance is yes-instance. Let #3SAT be the vector for an assignment of the Boolean variables satisfying the 3-SAT instance. Based on Observation 2 we now have h(#ASAT) = 0 implying the following inequality where ʃ(-) denotes the WACHTER-CFE. objective and OPTere denotes an optimal value for f()):
OPTCFE & OPTCFESf(EssSe f(ESSAT) & max
(11)
The algorithm A(-) is 20(") approxxmatto algorithm:
f(x.) & 2(()) OPTCFE
(12)
18

---

Published in Transactions on Machine Learning Research (12/2025)
21
no
yes
222 >
0
110
yes
yes
0
cM
Figure 3: For each clause in the 3-SAT instance, we have a decision tree in the additive tree model producing a high output if the clause is not satisfied. The figure shows decision tree for the example clause -01 V V /-3-
2: 2:22 2:
[o,
1 111
:0
1, 1, 0, 11111
21 .......:
0,,0,0, (0,000,2 21 ]::0
[0, 1, 21
:0
0, 0, 1 :1:0
|,1,,,,,
:
[1,0,0 0, 1
2
[100, 1, 1 11111
cM
1
21 21
x' = 1,
Figure 4: The figure shows the vectors in the regrregressor for the clause -I₁ Væz V -zs with labels after the colon symbol. The input vector does not satisfy the clause, so it closest to the vector with label cM.
We now get
[(xa) 20(n) max 0(=) (M 1)2
(13)
From Observation 2 we see that this inequality can only hold if h(wer) and that can build a satisfying assignment for the 3-SAT instance from Tet. In other words, the algorithm A(-) be used to compute assignment of the boolean variables satisfying the 3-SAT instance if such an assignment exists contradicting NP-P (here we use Observation I..
Proof of Theorem 2 We use the same strategy as in the proof of Theorem I We construct a simple additive model with a similar functionality as the neural network.
We build binary decision tree for each clause that will have output if the clause is satisfied and output cM otherwise where is the number of clauses. An example of such tree is shown in Fig 3 Observation and Observation 2 also hold for the additive tree model reduction, which concludes the proof.
Proof of Theorem D For a 3-SAT instance, we construct a simple kNN model with a similar functionality as the regressors the previous two reductions. To be more specific, we build a kNN-regressor consisting of Se vectors (c is the number of clanses). The output the regressor is the average of the labels of the vectors that closest to the input with respect to the Fuclidean distance.
19

---

Published in Transactions on Machine Learning Research (12/2025)
For each clause, construct 8 vectors corresponding to all the 8 possible assignments for the 3 boolean variables appearing in the clause. One of the vectors corresponds to the case where the clause is not satisfied, and this vector has the label cM, while the other 7 vectors have the label O. The 8 vectors for an example clause are shown in Fig.
The input vector x' is not satistying the clause if and only if the vector with label cM is closest x', implying that Observation holds. We also notice that Observation ! holds, which concludes the proof. ]
20


Reviews:
[{"review_id": "3qiawetf7J", "reviewer": "Reviewer_RLgA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths of the paper:\n\n1. The problem of counterfactual and semi-factual estimation is of significant importance given the rise of large language models and data privacy concerning these models, and there exists a lack of interpretability surrounding these models. This paper makes an attempt to solve that, by grouping together all the existing models and stating their respective complexities (Tables 1 and 2). An impactful contribution.\n\n2. The authors then introduce the problem on approximating these counterfactuals (semi-factuals) as opposed to finding the exact solutions, and demonstrate they can be hard to find. They prove this using a reduction from the 3-SAT problem. The authors construct regressors (e.g., a ReLU network, an additive tree model) that encode a 3-SAT instance, creating a large \"cost gap\" between satisfiable (\"yes\") and unsatisfiable (\"no\") instances. An efficient approximation algorithm could distinguish between these costs, thus solving 3-SAT, which is believed to be impossible. Proof is precise and accurate. \n\n3. The paper is very well written and easy to follow, with the problem statement being very clear in terms of clarity and impact.\n\nWeaknesses of the paper:\n\n1. Disconnect Between Survey and Novel Results: The paper's primary survey and background (Sections 2 and 3) are focused on classifiers, where the goal is to change a class label (e.g., Eqns 1, 3). However, the paper's main novel contribution (Section 4) proves inapproximability for the WACHTER-CFE formulation (Eq. 2), which is explicitly defined for a regressor using a squared error loss function. The link between the hardness of approximating this regressor problem and the hardness of the original classifier problem (finding the minimum-cost change to flip a label) is not made explicit.\n\n2. Ambiguity in Problem Formulations: The new proofs in Section 4 are for the single-objective WACHTER-CFE formulation (Eq. 2). Most of the surveyed literature, however, appears based on the constrained-optimization \"MCR\" formulation (Eq. 3). It is not immediately clear if the inapproximability results for the $\\lambda$-balanced objective (Eq. 2) directly apply to the MCR decision problem (Eq. 3).\n\n3. Not necessarily a weakness, but a consideration for future work in my opinion: The discussion (Section 5) rightly points out that NP-hard results mean optimal explanations are often infeasible, and practitioners must rely on heuristics. However, it doesn't deeply explore why these heuristics often find \"useful\" (if non-optimal) explanations. The paper focuses on worst-case complexity (proven via 3-SAT reductions) but doesn't discuss the gap between this and the average-case performance on real-world models. I believe that's one of the next steps of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the computational complexity of generating counterfactual and semi-factual explanations for machine learning models. The central finding is that for many common and complex models, finding these explanations is computationally hard (e.g., NP-hard), and often hard to even approximate. This has significant implications for the XAI community and the explainability of ML models in general.\n\nThe authors' contributions are twofold:\n\n1. Survey of counterfactual and semi-factual explanations of existing methods: The paper first provides a unifying framework of known complexity results. It summarises that while finding explanations for simple models like Decision Trees is efficient (PTIME), the problem becomes computationally hard for more powerful models. This includes being NP-complete for counterfactuals on ReLU Networks and kNN, and even $\\Sigma_{2}^{p}$-complete for plausible semi-factuals on these models.\n\n2. Inapproximability Results: This is the novel aspect of the paper. The authors propose inapproximability proofs for counterfactual and semi-factual finding and show that not only is finding exact optimal counterfactuals hard, but even finding approximate solutions is computationally difficult. Specifically, they prove (Theorems 1, 2, and 3) that for ReLU networks, additive tree models, and kNN models, no polynomial-time approximation algorithm exists (under the assumption $P \\ne NP$). \n\nTypically I look into 4 factors for judging a paper: Soundness, clarity, impact and novelty. The paper is very good in terms of the first three, while being novel on the inapproximation proof. Leaning towards acceptance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested changes:\n\n1. Explicitly Bridge the Classifier-Regressor Gap: The paper would be significantly strengthened if the authors, in Section 4, explicitly justify the shift to a regressor formulation for their new proofs. They should add a discussion on how the inapproximability of the WACHTER-CFE regressor problem translates to the \"classic\" CFE classifier problem (MCR, Eq. 3). For instance, can any MCR problem for a classifier be reduced to this regressor formulation, preserving the approximation hardness?\n\n2. Clarify the Choice of WACHTER-CFE: A brief paragraph could be added to Section 4 explaining why the WACHTER-CFE formulation (Eq. 2) was chosen for the inapproximability proofs over the MCR formulation (Eq. 3). This would help integrate the new contribution with the surveyed literature more tightly.\n\n3. Refine the Discussion on Practicality: The discussion in Section 5 could be expanded to be more actionable. Instead of just stating that heuristics are used, the authors could suggest that future work should move beyond worst-case complexity. They could propose analyzing the average-case complexity or parameterised complexity (e.g., complexity in terms of model depth rather than just total size) of these problems, which might better explain why heuristics are often \"good enough\" in practice.\n\n4. Contextualise \"Plausibility\" and \"Robustness\": The paper rightly identifies that the complexity of \"plausible\" and \"robust\" explanations is a key open area. It would be beneficial to add a sentence acknowledging that the definitions used in the literature so far (e.g., \"learning a separate function\") are just a few of many possible formalisations. This would frame the \"missing entries in Tables 1 and 2\" as an even richer field for future work, covering other definitions like causal plausibility or manifold-based robustness.", "broader_impact_concerns": "No Broader Impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kRie0UjbSh", "reviewer": "Reviewer_gJzN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n- The paper is well written and accessible, especially in its introduction and background. It provides adequate context and formalisation. Despite my limited background in complexity theory, I was able to follow most of the arguments.\n- The survey of existing work is extensive and well organised in tables.\n- To the best of my knowledge, the approximation hardness results are novel and well constructed, demonstrating that approximate counterfactual generation is also computationally intractable.\n\n\n# Weaknesses :\n- The readability of the inapproximability proofs could be improved. Furthermore, in Definition 2 (WACHTER-CFE), it would help to include the full objective function and define the function $f$ explicitly. Including more of the intuition for the construction in the main text, not just in the appendix, would make the results more accessible.\n- The 3-SAT reductions are interesting, but their novelty is hard to assess without a comparison to similar constructions in the literature. A brief discussion of related reduction techniques—especially in the context of approximation—would clarify the paper’s contribution.\n- Since optimal solutions are shown to be hard or inapproximable, a survey or commentary on heuristic or approximate methods in the literature would be a helpful complement to the hardness results.\n- The results are limited to discrete input domains.  It narrows the generality of the findings and the discussion in section 5. The implications for continuous domains (which are typical in many practical counterfactual generation setups) should be discussed further, especially in Section 5.\n- The authors raise the question of whether it is acceptable to use models for which computing explanations is infeasible. However, many counterfactual methods already rely on heuristics (e.g., gradient descent, adversarial losses) that produce approximate explanations. It would be helpful to relate the theoretical results to this practical reality.\n- A significant portion of the paper discusses semi-factual explanations, yet the main technical results pertain only to counterfactuals. Given the close relationship between the two (as noted in Alfano et al., 2025), the authors could do more to explore whether their techniques extend to semi-factuals.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper examines the computational complexity of generating counterfactual and semi-factual explanations. It begins with a concise introduction to both types of explanations and fundamental notions in computational complexity. It then surveys known results on the computational hardness of counterfactual generation and semi-factual generations across various model classes. From this setup, the authors derive two straightforward corollaries.\n\nWhile prior work primarily focuses on exact solutions, this paper extends the discussion to approximation complexity: the difficulty of approximating a counterfactual explanation, rather than computing it exactly. To this end, the authors construct hardness proofs by reducing the counterfactual approximation problem to 3-SAT for three model classes (MLPs, regression trees, and kNNs). Each construction defines models that output 0 if the 3-SAT instance is satisfiable, and a large value otherwise. The approximation threshold is engineered so that any solution outside a narrow band would be too far from the optimal value, thus would not lead to a solution to the 3-SAT problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Clarify the scope and assumptions of the inapproximability theorems—particularly discrete inputs—and consider briefly how these assumptions compare to real-world counterfactual setups. \n- Expand Section 5 to include a discussion of commonly used heuristic methods and how they fare in light of the intractability results. \n- Discuss the originality of the 3-SAT reduction strategy by comparing it to similar constructions in existing literature. For instance, briefly introducing similar constructions in other papers in the literature review would help understand the novelty of the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OG6nQHo3ci", "reviewer": "Reviewer_VsYR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* I believe that the study of the computational complexity of explainability methods in AI (and xAI in general) is a highly relevant topic with current impact.\n* The fact that this paper addresses not only counterfactual explanations but also semi-factual ones is, in my view, very positive (since semi-factuals represent a less explored area).\n\nWeaknesses: \n* In my humble opinion, the paper lacks a bit of depth and original contribution. It starts by discussing explainable AI, focusing on counterfactuals and semi-factuals; then it shifts, in a generic, introductory-tutorial style, to computational complexity classes; afterwards, it gives an overview of the literature findings on the computational complexity of counterfactual and semi-factual explanations. And up to this point, we have covered eight pages (out of the ten pages of the paper). In other words, up to this point we could say that no new knowledge has been generated at all.\n* Related with the previous point, the explanation of computational complexity classes (Section 2.2) seems a bit generic and unnecessary. For example, it discusses, among others, the coNP class, which is not mentioned or addressed again throughout the manuscript.\n* The conclusions of the paper are somewhat disappointing. For instance, one of the main points is: _\"We argue that it might be reasonable to move away from the idea to compute the 'best' (i.e., closest or optimal) counterfactual/semifactual, and instead aim for some counterfactual/semi-factual with reasonable properties such that it still remains useful in practice.\"_ This conclusion does not seem particularly novel or original. And I would argue that, in practical terms, this is already how counterfactuals are handled: you do not seek the optimal counterfactual, but one that is feasible to compute and useful for the specific practical case at hand.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors try to: \n* provide an overview of the literature analyzing the computational complexity of counterfactual and semi-factual explanations.\n* investigate the computational complexity of approximate solutions for counterfactual explanations. The authors conclude that explanations are often hard to generate and, under certain assumptions, they are also hard to approximate.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* The authors state that _\"This work focuses solely on this non-causal approach because all of the literature on the computational complexity of counterfactual explanations currently only considers the non-causal case.\"_ However, could the authors provide any insights and/or enrich the discussion regarding the computational complexity of causal counterfactuals?\n\n* There are some sentences that should be rephrased and/or explained in a clearer way. For instance, in page 8 the authors state that _\"no polynomial time (1 − o(1)) ln n-approximation algorithm exists for the MCR problem Eq. 3 for ReLU networks where n is the number of neurons unless NP = P.\"_  \n\n* The paper mentions robust and plausible counterfactual explanations several times, including in the appendices, but I think it never defines what is exactly meant by robustness or by plausibility. I know that the authors directly refer to the definitions by Marzari et al. (2024) and Amir et al. (2024) but, in order to make the paper a bit more self-contained in this aspect, I would try to present the concepts in the paper. \n\n* Typos: \n   * \"also known as as “even if” explanations\" $\\rightarrow$ \"also known as “even if” explanations\"\n   * the MSR acronym is defined twice: in page 3 and in page 7; the PI acronym is defined in page 3 but never used; the MCA acronym is defined in page 3 but never used; the acronyms FBDD and DL are defined twice in page 5; acronym kNN is presented in page 9 (\"k-nearest neighbors (kNN)\") when it has already been used 4 times. I guess CFE stands for \"CounterFactual Explanation\", but this should be clarified in the paper as well. \n   * footnote 1 in page 7, and footnote 3 in page 8 are (almost) the same... Why? Furthermore, both footnotes include the acronym \"FBDNN\" that has not been defined before. \n   * in page 9, if I am not mistaken, the hyperlink to Eq.2 is broken in \"Objective: minimize objective (2)\"", "broader_impact_concerns": "No concerns regarding ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)