A Strongly Exponential Separation of DNNFs from CNF Formulas

2014/11/07 by Bova, Simone, Capelli, Florent, Mengel, Stefan +1 · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1411.1995

Abstract

Decomposable Negation Normal Forms (DNNFs) are Boolean circuits in negation normal form where the subcircuits leading into each AND gate are defined on disjoint sets of variables. We prove a strongly exponential lower bound on the size of DNNFs for a class of CNF formulas built from expander graphs. As a corollary, we obtain a strongly exponential separation between DNNFs and CNF formulas in prime implicates form. This settles an open problem in the area of knowledge compilation (Darwiche and Marquis, 2002).

Cited by

• Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width

Related

• Parameterized Compilation Lower Bounds for Restricted CNF-formulas
• Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
• A Lower Bound on DNNF Encodings of Pseudo-Boolean Constraints
• Propagation complete encodings of smooth DNNF theories
• On the relation between structured d-DNNFs and SDDs