The aim of this paper is to pave the way for the computational intelligibility of Boolean classifiers.
As a baseline, we use 9 XAI queries from those considered in [1]}, which are summarized in
Table REF : EMC, DPI, and ECO are explanation queries, and
CIN, EIN, IMA, IIR, IMO, MCP are verification queries.Five additional
verification queries, namely CAM, EAM, MFR, MCJ, MCH, are considered in [1]}, but
they mainly trivialize or boils down to another query in the list when dealing with Boolean classifiers
– [1]} considers the more general case of multi-label classifiers, i.e., when more than two output classes are targeted.
Based on this portfolio of XAI queries, we examine 7 families of Boolean classifiers: decision trees, DNF formulae, decision lists,
random forests, boosted decision trees, Boolean multilayer perceptrons, and Boolean neural networks.
The main contribution of this paper lies in a number of complexity results establishing the existence
of a large intelligibility gap between families of classifiers, estimated by the number of XAI queries (over 9) which are tractable.
Specifically, we prove that all XAI queries are tractable for the family of decision trees, while none of them
is tractable for DNF formulae, decision lists, random forests, boosted trees, Boolean multilayer perceptrons, or of binarized neural networks.
