# Abductive explanations of classifiers under constraints: Complexity and properties

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 18 Sep 2024.

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

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits](https://mlsanity.com/paper/2301.13328/) (2023)

## Built on by (most cited first, 7 of 7)

- [On the Complexity of Global Necessary Reasons to Explain Classification](https://mlsanity.com/paper/2501.06766/) (2025)
- [The Explanation Game -- Rekindled (Extended Version)](https://mlsanity.com/paper/2501.11429/) (2025)
- [Axiomatic Foundations of Counterfactual Explanations](https://mlsanity.com/paper/2602.04028/) (2026)
- [Interpretable DNFs](https://mlsanity.com/paper/2505.21212/) (2025)
- [Towards Rigorous Explainability by Feature Attribution](https://mlsanity.com/paper/2604.15898/) (2026)
- [Fairness of Classifiers in the Presence of Constraints between Features](https://mlsanity.com/paper/2605.00592/) (2026)
- [Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding](https://mlsanity.com/paper/2609.04931/) (2026)

## Abstract (arXiv)

Abductive explanations (AXp's) are widely used for understanding decisions of classifiers. Existing definitions are suitable when features are independent. However, we show that ignoring constraints when they exist between features may lead to an explosion in the number of redundant or superfluous AXp's. We propose three new types of explanations that take into account constraints and that can be generated from the whole feature space or from a sample (such as a dataset). They are based on a key notion of coverage of an explanation, the set of instances it explains. We show that coverage is powerful enough to discard redundant and superfluous AXp's. For each type, we analyse the complexity of finding an explanation and investigate its formal properties. The final result is a catalogue of different forms of AXp's with different complexities and different formal guarantees.