---
title: "Updates on the Complexity of SHAP Scores"
authors:
  - "Xuanxiang Huang"
  - "Joao Marques-Silva"
doi: "10.24963/ijcai.2024/45"
url: "https://ijcai.org/proceedings/2024/45"
pdf: "https://ijcai.org/proceedings/2024/0045.pdf"
venue: "Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence"
year: 2024
pages: "403-412"
track: "Main Track"
keywords:
  - "AI Ethics, Trust, Fairness: ETF: Explainability and interpretability"
  - "AI Ethics, Trust, Fairness: ETF: Trustworthy AI"
  - "Knowledge Representation and Reasoning: KRR: Computational complexity of reasoning"
  - "Machine Learning: ML: Explainable/Interpretable machine learning"
---

# Updates on the Complexity of SHAP Scores

Xuanxiang Huang, Joao Marques-Silva

*Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence*, pages 403-412. DOI: [10.24963/ijcai.2024/45](https://doi.org/10.24963/ijcai.2024/45)

## Abstract

SHAP scores represent one of the most widely used methods of explainability by feature attribution, as illustrated by the explainable AI tool SHAP.
A number of recent works studied the computational complexity of the exact computation of SHAP scores, covering a comprehensive range of families of classifiers.
This paper refines some of the existing complexity claims, including families of classifiers for which the computation of SHAP scores is computationally hard and those for which there exist polynomial-time algorithms.