On the Complexity of Enumerating Prime Implicants from Decision-DNNF Circuits
Authors: Alexis de Colnet, Pierre Marquis
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study Enum IP from dec DNNF within the framework of enumeration complexity and prove that it is in Output P, the class of output polynomial enumeration problems, and more precisely in Inc P, 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. We provide evidence showing that enumerating specific prime implicants corresponding to subset-minimal abductive explanations or to sufficient reasons is not in Output P. |
| Researcher Affiliation | Academia | Alexis de Colnet1 and Pierre Marquis1,2 1Univ. Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), F-62300 Lens, France 2Institut Universitaire de France |
| Pseudocode | Yes | Algorithm 1: Missing IP(Σ, S, P); Algorithm 2: Generate IP(Σ); Algorithm 3: Propagate(Σ, t, P = (v0, . . . , vi)); Algorithm 4: Another IP(Σ, S) |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. It only provides a link to a full-proof version of the paper itself. |
| Open Datasets | No | This is a theoretical paper focusing on complexity classes and algorithms; it does not involve empirical training on datasets. Therefore, no information on public datasets for training is provided. |
| Dataset Splits | No | This is a theoretical paper focusing on complexity classes and algorithms; it does not involve empirical validation on datasets. Therefore, no information on dataset splits is provided. |
| Hardware Specification | No | This is a theoretical paper that focuses on algorithm design and complexity analysis. It does not describe any experiments that would require specific hardware, so no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper focused on algorithms and complexity theory. It does not provide details on specific software dependencies or their version numbers for replication of empirical experiments. |
| Experiment Setup | No | This is a theoretical paper that designs algorithms and analyzes their complexity. It does not involve empirical experiments, thus no experimental setup details like hyperparameters are provided. |