Structured d-DNNF Is Not Closed under Negation

Harry Vinall-SmeethIJCAI 2024

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:

  1. Sentential Decision Diagrams (SDDs): Highly tractable and canonical, supporting most operations in polynomial time.
  2. 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.
A v-tree (left) and a corresponding structured circuit (right) illustrating how variable decomposition guides the circuit's structure.

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.
Comparison between an arithmetic circuit (left) and a Boolean circuit (right), demonstrating the extension of these results to probabilistic models.

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

BibTeX
@inproceedings{vinallsmeeth2024structured,
  author = {Harry Vinall-Smeeth},
  title = {{Structured d-DNNF Is Not Closed under Negation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure