Enlarging the set of XAI queries that are used for the intelligibility assessment is another dimension for further research.
Among the computational queries that could be added to the intelligibility map is the ability (or not) to compute SHAP scores in a tractable way,
as investigated recently in [1]}, [2]}.
Deriving more fine-grained complexity results (i.e., not restricted to NP-hardness in the broad sense) and determining whether
the answers to some XAI queries can be approximated efficiently (under some guarantees on the quality of the approximation achieved) would be useful as well.
Finally, experiments will be also needed to determine to which extent the XAI queries we have considered in the paper are hard to be addressed in practice.
