On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits

Prime implicants can be efficiently enumerated from certain AI systems: The paper demonstrates that enumerating prime implicants from dec-DNNF circuits is computationally tractable (in OutputP and IncP classes), meaning this fundamental operation for AI explainability can be performed in polynomial time relative to the output size.

Explanations for AI predictions face harder computational challenges: When restricting prime implicants to represent "sufficient reasons"—explanations for why machine learning classifiers make specific predictions—the enumeration problem becomes significantly harder and likely falls outside the OutputP class, suggesting practical limits to generating these types of explanations at scale.

Abductive explanations have long-standing but computationally difficult foundations: The paper confirms that enumerating subset-minimal abductive explanations (a concept studied in AI for over 30 years) is computationally harder than general prime implicant enumeration, indicating that finding the most concise explanations for system behavior requires substantially more computational resources.

Explainability comes with computational trade-offs: The research reveals a hierarchy of computational difficulty in generating different types of explanations, suggesting that more useful or interpretable explanations (like sufficient reasons) may require accepting longer computation times or approximations rather than exact solutions.