On the Computational Intelligibility of Boolean Classifiers

Decision trees offer superior explainability: The paper finds that decision trees can answer all 9 types of XAI (explainable AI) queries in polynomial time, making them computationally tractable for explanation and verification tasks—a capability not shared by other common classifiers.

Popular ensemble methods lack computational intelligibility: Random forests and boosted decision trees, despite their widespread use in practice, cannot tractably answer any of the 9 XAI queries tested, revealing a significant gap between model popularity and explainability guarantees.

DNF formulae and neural networks present fundamental explainability challenges: The paper shows that DNF formulae, decision lists, Boolean multilayer perceptrons, and binarized neural networks all fail to provide tractable answers to XAI queries, suggesting inherent computational barriers to explaining these model classes.

There is a substantial "intelligibility gap" across classifier families: The stark contrast—where decision trees handle all queries while six other classifier families handle none—demonstrates that the choice of model architecture fundamentally determines whether explanations can be computed efficiently.

Explainability should factor into model selection: These findings suggest that organizations prioritizing responsible AI and transparency should consider the computational intelligibility of different classifiers as a key criterion when choosing between models, not just accuracy or performance metrics.