Abstract
We propose a method for compiling propositional theories into a new tractable form that we refer to as decomposable negation normal form (DNNF). We show a number of results about our compilation approach. First, we show that every propositional theory can be compiled into DNNF and present an algorithm to this effect. Second, we show that if a clausal form has a bounded treewidth, then its DNNF compilation has a linear size and can be computed in linear time - treewidth is a graphtheoretic parameter which measures the connectivity of the clausal form. Third, we show that once a propositional theory is compiled into DNNF, a number of reasoning tasks, such as satisfiability and forgetting, can be performed in linear time. Finally, we propose two techniques for approximating the DNNF compilation of a theory when the size of such compilation is too large to be practical. One of the techniques generates a sound but incomplete compilation, while the other generates a complete but unsound compilation. Together, these approximations bound the exact compilation from below and above in terms for their ability to answer queries.
Introduction
In artificial intelligence, automated reasoning often faces a "pay-as-you-go" computational challenge. Standard tasks like checking the satisfiability of a set of constraints are NP-complete, requiring significant resources for every query. Knowledge Compilation addresses this by performing intensive computation upfront to transform a logical theory into a "tractable" form. Once compiled, answering queries becomes significantly more efficient.
While previous efforts focused on formats like Horn theories, they often suffered from loss of information. This work introduces Decomposable Negation Normal Form (DNNF), a representation that is both universal—capable of representing any propositional theory—and tractable for a wide range of reasoning tasks.
Decomposable Negation Normal Form (DNNF)
DNNF is a subset of Negation Normal Form (NNF) characterized by the decomposability property. In a DNNF, for any conjunction (AND gate), the sub-theories represented by its children must involve disjoint sets of variables (atoms). This property is the key to ensuring that complex operations can be decomposed into independent, simpler sub-problems.
Compilation Methodology
The paper introduces recursive algorithms, DNNF1 and DNNF2, to perform this compilation. These procedures utilize case analysis, similar to Shannon expansion, to break down a theory into independent components.
A critical component of this process is the use of Decomposition Trees. By partitioning the clauses of a theory into a tree structure, the algorithm can systematically manage the complexity of the transformation. Furthermore, caching is employed to store the results of sub-problems, preventing redundant work and significantly speeding up the compilation of repetitive logical structures.
Theoretical Insights and Results
The research establishes several key properties of DNNF:
- Linear-Time Reasoning: Once a theory is in DNNF, tasks such as checking satisfiability or "forgetting" a variable (existential quantification) can be solved in $O(n)$ time, where $n$ is the size of the DNNF.
- Treewidth and Complexity: The complexity of compiling a theory is governed by its treewidth—a graph-theoretic measure of connectivity. If a theory has a bounded treewidth $w$, its DNNF compilation has a linear size $O(n \cdot 2^w)$ and can be computed in linear time.
- Compactness: For certain functions, such as the odd-parity function, DNNF provides an exponentially more compact representation than traditional formats like Disjunctive Normal Form (DNF).
Approximations and Limitations
For theories with high treewidth where exact compilation is computationally prohibitive, the paper proposes two approximation techniques: $DNNF_u$ (sound but incomplete) and $DNNF_l$ (complete but unsound). These provide upper and lower bounds for answering queries.
The primary limitation remains the exponential dependence on treewidth during the initial compilation phase. While DNNF is powerful, highly "tangled" logical theories may still result in representations that are too large for practical use. Future work involves developing optimized heuristics for variable selection during approximation and industrial-strength compiler implementations.
Summary updated