When an artificial intelligence denies a loan application, diagnoses a patient, or derives a complex logical conclusion, users naturally ask: Why?
Providing a complete trace of a system's internal mechanics is rarely helpful. As Chunxi Ji observes in On the Computation of Necessary and Sufficient Explanations, human users require the shortest possible sets of features to ensure the information remains cognitively manageable. We seek parsimony—the absolute minimum number of reasons required to guarantee an outcome.
However, a profound computational paradox underlies this requirement. Across machine learning, logic programming, and database systems, researchers have uncovered a shared mathematical reality: finding a valid explanation can be relatively straightforward, but proving that an explanation is minimal is exceptionally difficult. Forcing an explanation to be concise introduces a severe computational bottleneck, frequently elevating the problem into much higher complexity classes.
Why Minimality Explodes Complexity
To understand why brevity is so expensive, consider the difference between verification and optimization. If a system proposes an explanation for an event, verifying its validity simply requires checking if the proposed causes entail the effect.
However, verifying minimality requires proving a negative: you must demonstrate that no smaller subset of those causes could produce the same effect.
Valid Explanation Check:
[Cause A + Cause B + Cause C] ===> Does this trigger the effect? (Often Easy)
Minimal Explanation Check:
Does [Cause A + Cause B] trigger it?
Does [Cause B + Cause C] trigger it?
Does [Cause A + Cause C] trigger it? ... (Requires checking all subsets)
This subset-minimality check introduces an extra layer of quantification. In database query answering under existential rules, the authors of Query Answer Explanations under Existential Rules show that this requirement causes a sharp complexity jump. While finding a query answer might reside in one complexity class, confirming that a specific subset of facts constitutes a minimal justification requires moving up to a harder class (such as $\text{DP}$), because the algorithm must simultaneously verify entailment and ensure no smaller subset exists.
A similar bottleneck appears in automated planning and model reconciliation. When a robot explains its plan to a human by updating the human's mental model, providing a massive, complete description of the environment is computationally trivial. However, Sarath Sreedharan et al. demonstrate in On the Computational Complexity of Model Reconciliations that finding the smallest set of model updates is $\Sigma^P_2$-complete. The computational hardness is driven entirely by the requirement for minimality; the system must search through the vast space of possible updates while verifying that no shorter alternative plan becomes viable for the observer.
The Wall in Machine Learning Interpretability
This mathematical barrier is highly pronounced in modern explainable AI (XAI), where algorithms attempt to explain black-box neural networks by identifying the smallest subset of input features that preserves a prediction.
If a classifier relies on non-linear interactions, features cannot be evaluated in isolation. To find a globally minimal explanation, an algorithm must navigate an exponential combinatorial explosion of feature subsets. Stephan Waeldchen et al. mapped this boundary in The Computational Complexity of Understanding Binary Classifier Decisions, proving that finding the exact minimal feature set is $\text{NP}^{\text{PP}}$-complete. Crucially, the authors established that even approximating the size of the smallest explanation is NP-hard. This means popular heuristic interpretability tools cannot guarantee that the explanations they output are near-optimal; they may routinely produce explanations that are unnecessarily bloated or redundant.
This tension between speed and conciseness manifests across several XAI frameworks:
- Formal Verification: In VeriX: Towards Verified Explainability of Deep Neural Networks, Haoze Wu et al. leverage constraint solvers to generate mathematically sound explanations, but note that the search for a globally minimal set of influential features forces the system into solving NP-complete problems.
- Local Anchors: Sebastian Ordyniak et al. study the task of finding the smallest "anchor"—a concise local explanation that maintains high coverage across similar data points—in The Parameterized Complexity of Finding Concise Local Explanations. They confirm that the mathematical task of identifying the absolute smallest subset of anchoring features is generally NP-hard.
- Knowledge Compilation: To bypass these run-time costs, Adnan Darwiche suggests in Logic for Explainable AI compiling neural networks into symbolic logical functions. Yet, the underlying challenge remains: without efficient ways to extract minimal prime implicants, explanations remain too complex for human comprehension.
The Deep Roots in Symbolic Reasoning
The computational penalty of minimality is not a new artifact of deep learning; it is a foundational characteristic of symbolic logic and automated reasoning.
In propositional abduction—the process of finding the best logical hypothesis to explain an observation—the search space is notoriously difficult. Gustav Nordh et al. show in Propositional Abduction is Almost Always Hard that while determining whether any explanation exists can sometimes be managed, selecting an optimal explanation based on minimality criteria is almost always intractable. The optimization layer required to enforce subset-minimality is exceptionally difficult to encode efficiently in standard decision procedures, as noted by Andreas Pfandler et al. in Backdoors to Abduction.
When reasoning moves to non-monotonic frameworks—where adding new information can invalidate previous conclusions—the cost of parsimony escalates further. Thomas Eiter et al. demonstrated in Semantics and Complexity of Abduction from Default Theories that enforcing minimality in default logic adds an entire level of computational complexity. This occurs because verifying that no subset of the explanation works requires testing the explanation's validity across multiple potential world states.
This exact bottleneck reappears across diverse symbolic paradigms:
- Multi-Disorder Diagnosis: Even in early expert systems, Thomas D. Wu highlighted in Efficient Diagnosis of Multiple Disorders Based on a Symptom Clustering Approach that filtering out redundant causes to ensure a minimal diagnostic explanation introduces significant computational overhead when multiple diseases produce overlapping symptoms.
- Preference Inference: In multi-criteria decision analysis, Christophe Labreuche et al. show in Comparing Options with Argument Schemes Powered by Cancellation that while determining the validity of a preference inference is computationally efficient via linear programming, finding the shortest or most elegant symbolic explanation for that inference is NP-complete.
- Ontological Queries: When explaining missing query results ("why-not" explanations), Balder ten Cate et al. demonstrate in High-Level Why-Not Explanations using Ontologies that while identifying a general explanation is feasible, finding the shortest symbolic representation measured by the total number of symbols is NP-hard. Similarly, Ismail Ilkan Ceylan et al. establish in Explanations for Ontology-Mediated Query Answering in Description Logics (Extended Abstract) that generating minimal explanations is frequently harder than computing the query answer itself.
- Answer-Set Programming: In modern combinatorial solvers, Thomas Eiter et al. show in Explaining Answer-Set Programs with Abstract Constraint Atoms that identifying the most concise set of reasons for a logical conclusion reaches high levels of the polynomial hierarchy, forcing a strict tradeoff between explanation minimality and search tractability.
The Interpretability Paradox
The collective evidence across these distinct fields points to a fundamental Interpretability Paradox:
$$\text{Human Readability} \propto \frac{1}{\text{Explanation Size}}$$
$$\text{Algorithmic Complexity} \propto \frac{1}{\text{Explanation Size}}$$
The very characteristic that makes an explanation valuable to a human—its brevity—is precisely what makes it computationally expensive for a machine to discover. As systems become more complex, balancing the cognitive limits of the human user against the mathematical limits of the algorithm remains one of the most significant challenges in explainable AI.
Key Foundational Work
Efficient Diagnosis of Multiple Disorders Based on a Symptom Clustering Approach (1990) — contributed 1 concept elements to this direction.
Computational Complexity of Hypothesis Assembly (1987) — contributed 1 concept elements to this direction.