# On Compiling DNNFs without Determinism

arXiv: https://arxiv.org/abs/1709.07092 · HTML: https://mlsanity.com/paper/1709.07092/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Sep 2017.

## Built on by (most cited first, 4 of 4)

- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation](https://mlsanity.com/paper/2303.06516/) (2023)
- [To Neuro-Symbolic Classification and Beyond by Compiling Description Logic Ontologies to Probabilistic Circuits](https://mlsanity.com/paper/2601.14894/) (2026)
- [Pruning Boolean d-DNNF Circuits Through Tseitin-Awareness](https://mlsanity.com/paper/2407.17951/) (2024)

## Abstract (arXiv)

State-of-the-art knowledge compilers generate deterministic subsets of DNNF, which have been recently shown to be exponentially less succinct than DNNF. In this paper, we propose a new method to compile DNNFs without enforcing determinism necessarily. Our approach is based on compiling deterministic DNNFs with the addition of auxiliary variables to the input formula. These variables are then existentially quantified from the deterministic structure in linear time, which would lead to a DNNF that is equivalent to the input formula and not necessarily deterministic. On the theoretical side, we show that the new method could generate exponentially smaller DNNFs than deterministic ones, even by adding a single auxiliary variable. Further, we show that various existing techniques that introduce auxiliary variables to the input formulas can be employed in our framework. On the practical side, we empirically demonstrate that our new method can significantly advance DNNF compilation on certain benchmarks.