Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings

Petr Kucera, Petr SavickýAAAI 2021 · DOI

Abstract

Knowledge Compilation (KC) is a central paradigm in artificial intelligence for handling hard propositional logic problems by pre-processing them into tractable target languages. This paper introduces Backdoor Decomposable Monotone Circuits (BDMCs), a novel framework that generalizes Decomposable Negation Normal Forms (DNNFs) by allowing complex logical encodings at the leaves. We focus on Propagation Complete (PC) encodings, demonstrating that PC-BDMCs are strictly more succinct than DNNFs while remaining computationally efficient. We provide a polynomial-time flattening construction that transforms a smooth PC-BDMC into a single PC encoding, effectively placing this new language on the Knowledge Compilation Map.

Introduction

The efficiency of modern SAT solvers often hinges on unit propagation. In the field of Knowledge Compilation, researchers seek target languages that balance succinctness (representation size) with tractability (the ability to answer queries in polynomial time). While DNNFs have long been the gold standard, their exponential size in certain domains limits their applicability. This work explores whether incorporating the power of unit propagation directly into the circuit structure can yield more compact representations.

Methodology: Backdoor Decomposable Monotone Circuits

A BDMC is a logic circuit composed of AND and OR gates where the leaves are not restricted to simple literals but can be entire CNF encodings from a specific class $\mathcal{C}$. The authors specifically investigate the class of Propagation Complete (PC) encodings. A formula is PC if unit propagation is sufficient to derive all implied literals or detect a contradiction.

The Flattening Construction

A key contribution of this work is the proof that a smooth PC-BDMC is polynomially equivalent to a single PC encoding. To achieve this, the authors utilize an Extended Implicational Dual Rail Encoding. This technique represents each logical literal using two meta-variables, allowing the circuit's structural dependencies to be simulated through unit propagation within a flat CNF formula.

Table of clauses for the Extended Implicational Dual Rail Encoding used in the flattening construction.

The construction involves defining specific clauses (as shown in the table above) that link the internal nodes of the circuit to the leaf encodings, ensuring that the propagation properties of the original BDMC are preserved in the resulting flat encoding.

Key Insights and Results

The theoretical analysis establishes several critical properties of PC-BDMCs:

  1. Succinctness Breakthrough: PC-BDMCs are proven to be strictly more succinct than DNNFs. There exist logical functions that can be represented by a polynomial-sized PC-BDMC but require an exponentially large DNNF.
  2. Polynomial Equivalence: The ability to transform a circuit of PC encodings into a single PC encoding in polynomial time (Theorem 1) ensures that the hierarchical structure does not add more complexity than the base class can handle.
  3. Tractability: PC-BDMCs support essential KC queries, such as consistency checking and model enumeration, in polynomial time. They also support transformations like conditioning and existential quantification (forgetting).

Discussion and Future Work

While PC-BDMCs offer superior succinctness, identifying whether a given formula is Propagation Complete is a co-NP-complete problem. This poses a challenge for automated compilation. However, the authors suggest that existing DNNF compilers, such as D4, could be adapted to produce BDMCs by terminating the decomposition process early when a PC component is identified. Future research may explore other base classes for leaves, such as Horn or 2-CNF formulas, to further refine the Knowledge Compilation Map.

Conclusion

By bridging the gap between structural circuit benefits and the efficiency of unit propagation, BDMCs provide a powerful new target language for Knowledge Compilation. Their strict succinctness over DNNFs marks a significant theoretical advancement in the representation of complex logical constraints.

Summary updated

BibTeX
@inproceedings{kucera2021backdoor,
  author = {Petr Kucera and Petr Savický},
  title = {{Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16501},
}
Figure