Addressing such XAI queries requires the availability of inference algorithms for computing answers in reasonable time.
From this perspective, each query can be viewed as a property that a family of classifiers may offer or not:
it is offered when there exists a polynomial-time algorithm to answer the query from any classifier of the family, and it is not
when there is no such algorithm, unless P = NP. In other words, the computational intelligibility of a family of classifiers
can be defined as the set of tractable XAI queries supported by the family, leading to an intelligibility map when several families of classifiers
are considered. Such an approach echoes the computational evaluation of KR languages
achieved in the knowledge compilation map [1]}.
