# On the Computation of Necessary and Sufficient Explanations

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 52 references that are in the map.
- First posted on arXiv 20 Mar 2022.

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

- ["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)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Counterfactual Visual Explanations](https://mlsanity.com/paper/1904.07451/) (2019)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Explaining Explanations in AI](https://mlsanity.com/paper/1811.01439/) (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)
- [Verifying Properties of Binarized Deep Neural Networks](https://mlsanity.com/paper/1709.06662/) (2017)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [Contrastive Explanations with Local Foil Trees](https://mlsanity.com/paper/1806.07470/) (2018)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Probabilistic Sufficient Explanations](https://mlsanity.com/paper/2105.10118/) (2021)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)
- [On Quantifying Literals in Boolean Logic and Its Applications to Explainable AI](https://mlsanity.com/paper/2108.09876/) (2021)
- [On Symbolically Encoding the Behavior of Random Forests](https://mlsanity.com/paper/2007.01493/) (2020)
- [Efficient Explanations for Knowledge Compilation Languages](https://mlsanity.com/paper/2107.01654/) (2021)
- [On the Relative Succinctness of Sentential Decision Diagrams](https://mlsanity.com/paper/1802.04544/) (2018)
- [On the Explanatory Power of Decision Trees](https://mlsanity.com/paper/2108.05266/) (2021)
- [Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases](https://mlsanity.com/paper/1309.6815/) (2013)
- [New Limits for Knowledge Compilation and Applications to Exact Model Counting](https://mlsanity.com/paper/1506.02639/) (2015)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [A New Class of Explanations for Classifiers with Non-Binary Features](https://mlsanity.com/paper/2304.14760/) (2023)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic](https://mlsanity.com/paper/2407.10820/) (2024)
- [Change in Quantitative Bipolar Argumentation: Sufficient, Necessary, and Counterfactual Explanations](https://mlsanity.com/paper/2509.18215/) (2025)
- [Explaining Decisions in ML Models: a Parameterized Complexity Analysis](https://mlsanity.com/paper/2407.15780/) (2024)
- [Sufficient and Necessary Explanations (and What Lies in Between)](https://mlsanity.com/paper/2409.20427/) (2024)
- [FAME: Formal Abstract Minimal Explanation for Neural Networks](https://mlsanity.com/paper/2603.10661/) (2026)
- [Local-to-Global Logical Explanations for Deep Vision Models](https://mlsanity.com/paper/2601.13404/) (2026)
- [Circuit Representations of Random Forests with Applications to XAI](https://mlsanity.com/paper/2602.08362/) (2026)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Feature Relevancy, Necessity and Usefulness: Complexity and Algorithms](https://mlsanity.com/paper/2505.09640/) (2025)
- [Uncovering Bugs in Formal Explainers: A Case Study with PyXAI](https://mlsanity.com/paper/2511.03169/) (2025)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [Efficient & Correct Predictive Equivalence for Decision Trees](https://mlsanity.com/paper/2509.17774/) (2025)
- [Explaining Decisions in ML Models: a Parameterized Complexity Analysis (Part I)](https://mlsanity.com/paper/2511.03545/) (2025)
- [Scaling the Explanation of Multi-Class Bayesian Network Classifiers](https://mlsanity.com/paper/2603.14594/) (2026)
- [Dsat: A Native SAT Solver for Discrete Logic](https://mlsanity.com/paper/2605.09347/) (2026)
- [GLARE: A Natural Language Interface for Querying Global Explanations](https://mlsanity.com/paper/2606.19735/) (2026)

## Abstract (arXiv)

The complete reason behind a decision is a Boolean formula that characterizes why the decision was made. This recently introduced notion has a number of applications, which include generating explanations, detecting decision bias and evaluating counterfactual queries. Prime implicants of the complete reason are known as sufficient reasons for the decision and they correspond to what is known as PI explanations and abductive explanations. In this paper, we refer to the prime implicates of a complete reason as necessary reasons for the decision. We justify this terminology semantically and show that necessary reasons correspond to what is known as contrastive explanations. We also study the computation of complete reasons for multi-class decision trees and graphs with nominal and numeric features for which we derive efficient, closed-form complete reasons. We further investigate the computation of shortest necessary and sufficient reasons for a broad class of complete reasons, which include the derived closed forms and the complete reasons for Sentential Decision Diagrams (SDDs). We provide an algorithm which can enumerate their shortest necessary reasons in output polynomial time. Enumerating shortest sufficient reasons for this class of complete reasons is hard even for a single reason. For this problem, we provide an algorithm that appears to be quite efficient as we show empirically.