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

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

Alexis de Colnet, Pierre Marquis

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 2583-2590. https://doi.org/10.24963/ijcai.2022/358

We consider the problem Enum·IP of enumerating prime implicants of Boolean functions represented by decision decomposable negation normal form (dec-DNNF) circuits. We study Enum·IP 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 thirty years. 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.
Keywords:
Knowledge Representation and Reasoning: Knowledge Compilation and Tractable Languages