As machine learning models are increasingly deployed in high-stakes domains like medicine, finance, and autonomous driving, the demand for explainability has shifted from informal heuristics (such as SHAP or LIME) toward formal explanations. A formal explanation provides a mathematically verifiable guarantee for a model's decision. For instance, an abductive explanation identifies a minimal set of features that completely forces a specific prediction, while a counterfactual explanation identifies the minimal change required to flip that prediction.
However, a profound theoretical bottleneck looms over this field: generating these rigorous explanations is often vastly more computationally expensive than generating the predictions themselves. A growing body of literature demonstrates that finding minimal, complete, or even loosely approximate explanations is inherently intractable across almost all non-trivial model architectures.
The Combinatorial Explosion of Minimality
Why is explaining a model so hard? The core difficulty stems from the requirement of minimality or completeness. To prove that a specific set of features is sufficient to explain a decision, an algorithm must verify that no subset or alternative configuration can violate that decision. This requirement transforms an explanation query into a massive search problem over an exponential space of feature combinations.
As a result, these tasks frequently land in severe complexity classes. Ignatiev et al. in On Relating Explanations and Adversarial Examples highlight that formal explanation frameworks utilizing logic oracles face massive $\text{NP}$-hard bottlenecks. Even for models traditionally viewed as highly interpretable, such as decision trees or random forests, the math remains unforgiving. Izza et al. proved in On Explaining Random Forests with SAT that deciding whether a minimal set of conditions is sufficient for a random forest prediction is $\text{DP}$-complete.
Going further, Jaakkola et al. showed in Explainability via Short Formulas: the Case of Propositional Logic with Implementation that finding the absolute shortest logical formula explaining a classifier's decision is $\Sigma^P_2$-complete—a complexity class sitting strictly above $\text{NP}$ that represents problems requiring an exponential number of $\text{NP}$ queries.
The Wall of Inapproximability
When an exact optimization problem is $\text{NP}$-hard, the standard engineering recourse is to settle for a good approximation. If we cannot find the absolute smallest counterfactual change or the absolute minimal feature set, can we find one that is within a reasonable factor (e.g., $2\times$ or $10\times$) of the optimum in polynomial time?
The most striking finding in this research direction is that for many common architectures, approximation is also impossible. In On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI, Artelt et al. (and their subsequent work On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI) proved that architectures like ReLU neural networks, additive tree models, and $k$-nearest neighbors ($k\text{NN}$) exhibit exponential inapproximability. Assuming $\text{P} \neq \text{NP}$, no polynomial-time algorithm can guarantee an explanation within even an exponential factor of the optimal solution.
The intuition behind this lies in the structural topology of the models' decision boundaries. The decision surfaces of ReLU networks or tree ensembles can form highly convoluted, fragmented, and non-convex geometries. Finding a valid counterfactual point requires navigating these fragmented spaces; a slight deviation can land the explanation in an entirely different decision region, rendering loose guarantees mathematically impossible to maintain efficiently.
The Compounding Cost of Real-World Constraints
In practice, an explanation is useless if it is completely unrealistic. If a counterfactual suggests that an applicant can get a loan by changing their age to a negative number or doubling their income while keeping their job experience at zero, the explanation fails human plausibility.
However, forcing explanations to respect real-world constraints compounds the computational hardness. Amir et al. demonstrated this in Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. They showed that even when a model's internal structure makes it easy to isolate a raw mathematical explanation, forcing that explanation to remain "in-distribution" via a distribution detector immediately elevates the task to $\text{NP}$-completeness or worse.
Similarly, Artelt et al. showed that adding constraints like plausibility or robustness (ensuring the explanation remains stable if the model weights are slightly updated) preserves or worsens this severe intractability. The explanation generator must not only reason about the model's internal logic but also simultaneously solve the hard problem of validating data distributions or multi-attribute preferences (Maudet et al.).
Complexity Reversals and Structural Limits
This computational lens also reveals counterintuitive structural properties of models. For example, we often assume that local explanations (explaining a single prediction) are easier than global ones (explaining the entire model). However, Bassan et al. in Local vs. Global Interpretability: A Computational Complexity Perspective uncovered a "complexity reversal": while linear models are easier to explain locally than globally, the inverse is true for neural networks and decision trees. For these complex models, finding a global summary can sometimes be computationally simpler than verifying the exact, rigorous boundaries of a single local prediction.
Furthermore, these hardness bounds are deeply entrenched; de Colnet et al. showed in On Translations between ML Models for XAI Purposes that these intractability properties seamlessly transfer between model classes whenever one model can be efficiently translated into another.
Coping with Intractability
Given these severe theoretical bounds, how can formal explainability be deployed in practice? The answer lies in shifting from worst-case complexity to average-case efficiency by leveraging advanced automated reasoning tools.
Instead of designing custom polynomial-time heuristics that sacrifice rigor, researchers use modern Boolean Satisfiability (SAT) solvers, Answer Set Programming (ASP), and specialized logical languages (Bustamante et al.). For instance, Audemard et al. in On the Computation of Example-Based Abductive Explanations for Random Forests demonstrated that counter-example guided refinement can efficiently find rigorous, example-anchored explanations for ensemble models within practical time limits for most real-world instances.
By treating the machine learning model as a complex logic circuit (Huang et al.), these approaches allow practitioners to navigate the worst-case exponential walls of explanation generation, providing exact answers where heuristics fall short.
Key Foundational Work
Minimal and Complete Explanations for Critical Multi-attribute Decisions (2011) — contributed 3 concept elements to this direction.
On Relating Explanations and Adversarial Examples (2019) — contributed 1 concept elements to this direction.