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.

研究了基于决策可分离负范式电路的布尔函数主要子句的枚举问题EnumIP，将其归纳于枚举复杂度的框架内，并证明它在OutputP与IncP中。此外，研究了两个更具挑战性的限制问题，其中一个是关于表示部分最小诱导解释的子句的问题，另一个则涉及到了可解释人工智能领域中的重要概念 - 具有合理原因的主要子句，最后还提供了一些可行性证据。

从 Decision-DNNF 电路枚举主合取范式的复杂度研究