Explaining Classification Through Global Sufficient Reasons and its Complexity

In recent years, explainable AI has become a major focus of research, driven by the need to better understand how AI systems arrive at their decisions in order to ensure trust and effective deployment. A central challenge in this field is the explanation of classifiers. Existing approaches typically distinguish between local explanations, which account for a classifier’s decision on an individual input, and global explanations, which aim to characterize the classifier’s behavior as a whole, independent of any particular input. This work concentrates on global explanations and characterizes classification decisions through "maximal" sufficient conditions that, when satisfied, guarantee that the classifier assigns the desired class to any input. We present a detailed analysis of the computational complexity of key problems in this setting across several important families of classifiers considered in the literature.