On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results.
Marcelo ArenasPablo BarcelóLeopoldo E. BertossiMikaël MonetPublished in: CoRR (2021)
Keyphrases
- knowledge compilation
- product configuration
- polynomial size
- computational complexity
- constraint satisfaction
- tractable cases
- prime implicates
- np complete
- logical inference
- decision problems
- pspace complete
- normal form
- quantified boolean formulae
- computer aided
- causal models
- boolean functions
- knowledge based systems
- knowledge discovery
- databases