A Compiler for Deterministic, Decomposable Negation Normal Form

Adnan DarwicheAAAI 2002 · OpenReview

Abstract: We present a compiler for converting CNF formulas into deterministic, decomposable negation normal form (d-DNNF). This is a logical form that has been identified recently and shown to support a number of operations in polynomial time, including clausal entailment; model counting, minimization and enumeration; and probabilistic equivalence testing. d-DNNFs are also known to be a superset of, and more succinct than, OBDDs. The polytime logical operations supported by d-DNNFs are a subset of those supported by OBDDs, yet are sufficient for model-based diagnosis and planning applications. We present experimental results on compiling a variety of CNF formulas, some generated randomly and others corresponding to digital circuits. A number of the formulas we were able to compile efficiently could not be similarly handled by some state-of-the-art model counters, nor by some state-of-the-art OBDD compilers.

TL;DR

This paper introduces a powerful compiler that converts complex logic formulas (CNF) into a highly efficient format called d-DNNF. By combining structural decomposition with advanced caching techniques, the compiler successfully handles "hard" problems—like random 3CNF formulas and digital circuits—that cause traditional tools like OBDD compilers and model counters to fail.

The Challenge of Knowledge Compilation

In artificial intelligence and formal verification, we often need to reason about complex logical formulas. While representing these problems in Conjunctive Normal Form (CNF) is easy, answering questions like "How many solutions exist?" (model counting) or "Are these two circuits equivalent?" is computationally brutal (NP-hard or worse).

To solve this, researchers use Knowledge Compilation: they translate the CNF into a "tractable" form where these queries can be answered in polynomial time. For years, Ordered Binary Decision Diagrams (OBDDs) were the gold standard. However, OBDDs have a major weakness: for many practical problems, they explode in size, becoming too large to fit in memory. This paper tackles the challenge of compiling into Deterministic, Decomposable Negation Normal Form (d-DNNF), a more expressive and succinct representation that promises to handle the cases where OBDDs fail.

Example of a d-DNNF structure showing the logical hierarchy of or/and gates.

Methods: The CNF2DDNNF Algorithm

The author presents an algorithm called CNF2DDNNF. Its core strategy is a "divide and conquer" approach guided by a data structure called a dtree (decomposition tree). Key components include:

  • Case Analysis (Shannon Expansion): The algorithm picks a variable, assumes it's true, solves the subproblem, then assumes it's false and solves the other side.
  • Decomposition: It uses the dtree to identify when a problem can be split into independent sub-problems that don't share variables.
  • Advanced Caching: Unlike previous versions that cached results based on specific variable assignments, this compiler caches based on the resulting sub-formula. This allows it to recognize that two different paths in the search tree have led to the exact same logical problem, drastically reducing redundant work.
  • Hypergraph Partitioning: To build efficient dtrees, the compiler treats the CNF formula as a hypergraph and uses partitioning algorithms to minimize the "connectivity" between sub-problems.

Experimental Evaluation

The compiler was evaluated against several standard benchmarks:

  • SATLIB: Random 3CNF formulas (uf50 to uf200) and graph coloring problems (flat100, flat200).
  • ISCAS85 & ISCAS89: Standard benchmarks for digital circuits (both combinational and sequential).
  • Planning Problems: Blocks-world and logistics formulas from the SATLIB repository.

Key Results and Insights

  • Succinctness is Real: The paper provides empirical proof for a theoretical claim: d-DNNFs are strictly more succinct than OBDDs. The compiler was able to generate compact d-DNNF representations for circuits where OBDD compilers (like the state-of-the-art CUDD) simply ran out of time or memory.
  • Outperforming OBDDs: For the uf100 random formulas, the d-DNNF compiler finished in seconds, while the CUDD OBDD compiler couldn't finish a single instance within four hours.
  • Circuit Mastery: The compiler successfully produced full behavior representations for all ISCAS85 circuits. For the c432 circuit, the d-DNNF had only ~2,900 nodes, whereas the best OBDD found had over 15,000.
  • Complexity Peaks: The research identified that for random 3CNF formulas, the peak compilation difficulty occurs at a clause-to-variable ratio of approximately 1.8—much lower than the 4.3 ratio typically associated with SAT solver difficulty.
Graph showing the compilation complexity peak for random 3CNF formulas at a clause-to-variable ratio of approximately 1.8.

Limitations and Future Work

While the results are promising, the author notes several areas for improvement. The current implementation is in LISP; a C implementation would likely be significantly faster. Additionally, the compiler currently handles single-rooted formulas; supporting "multi-rooted" d-DNNFs would be necessary to efficiently represent circuits with multiple outputs in a shared format. Finally, because the hypergraph partitioning used to build dtrees is randomized, finding the "optimal" dtree remains an open challenge.

Summary updated

Abstract

We present a compiler for converting CNF formulas into deterministic, decomposable negation normal form (d-DNNF). This is a logical form that has been identified recently and shown to support a number of operations in polynomial time, including clausal entailment; model counting, minimization and enumeration; and probabilistic equivalence testing, d-DNNFs are also known to be a superset of, and more succinct than, OBDDs. The polytime logical operations supported by d-DNNFs are a subset of those supported by OBDDs, yet are sufficient for model-based diagnosis and planning applications. We present experimental results on compiling a variety of CNF formulas, some generated randomly and others corresponding to digital circuits. A number of the formulas we were able to compile efficiently could not be similarly handled by some state-of-the-art model counters, nor by some state-of-the-art OBDD compilers.
BibTeX
@inproceedings{darwiche2002compiler,
  author = {Adnan Darwiche},
  title = {{A Compiler for Deterministic, Decomposable Negation Normal Form}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
  url = {https://openreview.net/forum?id=HkNvclWOZB},
}
Figure