Abstract
Knowledge compilation aims to represent Boolean functions in formats that balance succinctness with tractability. For over a decade, the relationship between Sentential Decision Diagrams (SDDs) and structured decomposable negation normal forms (structured d-DNNFs) remained partially understood. This paper resolves several open questions by proving that structured d-DNNF is not closed under negation, disjunction, or existential quantification. Furthermore, it establishes a formal succinctness gap, demonstrating that structured d-DNNFs can be significantly smaller than SDDs for certain Boolean functions.
Introduction
In the field of knowledge compilation, researchers seek to identify representations of Boolean functions that are both compact and support efficient queries and transformations. This involves a fundamental trade-off: as a representation becomes more expressive (succinct), it often loses tractability for operations like conjunction ($f \wedge g$) or negation ($\neg f$).
The "Knowledge Compilation Map" provides a taxonomy of these formats. Two prominent classes are:
- Sentential Decision Diagrams (SDDs): Highly tractable and canonical, supporting most operations in polynomial time.
- Structured d-DNNF: A broader class encompassing SDDs. While known to support efficient conjunction, its closure under negation and its succinctness relative to SDDs were long-standing open problems.
Methodology: Lifting and Permutations
The author employs techniques from communication complexity to derive these lower bounds. The proof strategy relies on two primary pillars:
Lifting Theorems
By adapting constructions from Knop (2017), the author "lifts" results from a fixed-partition communication model to a best-partition model. This is critical because the size of a structured d-DNNF is intrinsically linked to the best-partition complexity of the function it represents.
Permutation Construction
To establish the succinctness gap, the author constructs a specific function by "masking" a known hard function with permutations. This construction ensures that regardless of how an SDD attempts to partition variables (via its underlying v-tree), it inevitably encounters a computationally difficult instance of the function.
Key Insights
The research reveals that the "structure" provided by v-trees is not a panacea for tractability. While v-trees offer a systematic way to decompose functions, they do not inherently grant the algebraic properties found in SDDs. The "strong determinism" required by SDDs—which structured d-DNNFs lack—is the essential ingredient for closure under negation.
The "Negation Wall" identified in this paper shows that negating a structured d-DNNF can result in a quasi-exponential blow-up in size. This confirms that structured d-DNNF occupies a unique position: it is more compact than SDDs but significantly less tractable for bottom-up compilation tasks.
Results and Implications
The paper presents several landmark theorems:
- Theorem 1 (Succinctness Gap): There exist functions $f$ with structured d-DNNFs of size $s$ where any equivalent SDD requires size $s^{\Omega(\log s)}$.
- Theorem 2 (Non-closure): A function $f$ may have a polynomial-sized structured d-DNNF, yet its negation $\neg f$ requires quasi-exponential size.
- Transformation Limits: Structured d-DNNF is proven not to be closed under disjunction or existential quantification in polynomial time.
Furthermore, these results extend to Arithmetic Circuits (ACs). The succinctness gap persists in the probabilistic domain, showing that Probabilistic SDDs (PSDDs) can be exponentially larger than their structured-decomposable arithmetic circuit counterparts.
Conclusion and Future Directions
This work settles a decade-old debate, refining our understanding of the Knowledge Compilation Map. While the proven gap is quasi-polynomial, future research may determine if a fully exponential separation exists. Additionally, the closure properties of unstructured d-DNNFs remain an open challenge, likely requiring advancements in multi-partition communication complexity.
Summary updated