  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.
