On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits
This addresses foundational complexity issues in AI for explainability, particularly for abductive reasoning and machine learning classifiers, but is incremental in enumeration complexity theory.
The paper tackles the problem of enumerating prime implicants from decision-DNNF circuits, showing it is in polynomial incremental time, but proves that enumerating specific types like subset-minimal abductive explanations or sufficient reasons is likely not in output polynomial time.
We consider the problem EnumIP of enumerating prime implicants of Boolean functions represented by decision decomposable negation normal form (dec-DNNF) circuits. We study EnumIP from dec-DNNF within the framework of enumeration complexity and prove that it is in OutputP, the class of output polynomial enumeration problems, and more precisely in IncP, the class of polynomial incremental time enumeration problems. We then focus on two closely related, but seemingly harder, enumeration problems where further restrictions are put on the prime implicants to be generated. In the first problem, one is only interested in prime implicants representing subset-minimal abductive explanations, a notion much investigated in AI for more than three decades. In the second problem, the target is prime implicants representing sufficient reasons, a recent yet important notion in the emerging field of eXplainable AI, since they aim to explain predictions achieved by machine learning classifiers. We provide evidence showing that enumerating specific prime implicants corresponding to subset-minimal abductive explanations or to sufficient reasons is not in OutputP.