  In this paper, we investigate the computational intelligibility of Boolean
classifiers, characterized by their ability to answer XAI queries in polynomial
time. The classifiers under consideration are decision trees, DNF formulae,
decision lists, decision rules, tree ensembles, and Boolean neural nets. Using
9 XAI queries, including both explanation queries and verification queries, we
show the existence of large intelligibility gap between the families of
classifiers. On the one hand, all the 9 XAI queries are tractable for decision
trees. On the other hand, none of them is tractable for DNF formulae, decision
lists, random forests, boosted decision trees, Boolean multilayer perceptrons,
and binarized neural networks.
