On complexity of restricted fragments of Decision DNNF

This paper investigates the complexity of restricted fragments of Decision DNNF, specifically $\wedge_d$-OBDD and Structured Decision DNNF, by establishing lower bounds for CNFs of bounded incidence treewidth, demonstrating exponential separations between various models, identifying efficient cases for the Apply operation, and introducing a relaxed model called Structured $\wedge_d$-FBDD that effectively handles CNFs of bounded incidence treewidth.

The Gist

Imagine you are trying to solve a massive, complicated puzzle. In the world of computer science, this puzzle is a Boolean formula (a giant "Yes/No" question made of many smaller conditions). To solve these efficiently, computers use special "blueprints" or maps called Knowledge Compilation Models.

This paper is about studying two specific types of blueprints: Decision DNNF and its stricter cousins, $\land$d-obdds. The authors are asking: How good are these blueprints at handling puzzles that have a specific kind of complexity?

Here is the breakdown of their findings, translated into everyday analogies.

1. The Two Types of Complexity: "Primal" vs. "Incidence"

To understand the problem, imagine a puzzle made of Variables (the pieces) and Clauses (the rules connecting the pieces).

• Primal Treewidth (The "Local" View): Imagine the rules only connect pieces that are sitting right next to each other on a table. The puzzle is "locally" simple.
  • The Good News: The authors confirm that for these "locally simple" puzzles, the blueprints they study are very efficient. They can represent the solution in a size that grows reasonably with the puzzle's complexity.
• Incidence Treewidth (The "Global" View): Now, imagine the rules are wild. One rule might connect a piece on the far left to a piece on the far right, and another connects a piece in the middle to the top. The connections are scattered everywhere.
  • The Big Question: Can these blueprints still handle these "globally messy" puzzles efficiently?
  • The Answer: No. The paper proves that for these messy puzzles, the blueprints explode in size. They become exponentially huge, making them useless for large problems.

2. The "Rigid" vs. "Flexible" Blueprint

The authors compare two types of blueprints:

• The Flexible One (FBDD): Think of this as a choose-your-own-adventure book. You can ask questions in any order that makes sense for the current page. If a path gets tricky, you can jump to a different strategy.
• The Rigid One ($\land$d-obdd): This is like a train on a fixed track. You must ask questions in a specific, pre-determined order (e.g., always ask about Variable A, then B, then C). You cannot change the order, even if it would make the puzzle easier.

The Surprise Finding:
Usually, adding "smart gates" (the $\land$-nodes) to a rigid train track makes it much more powerful. The authors found that while the flexible book can simulate the rigid train with only a tiny bit of extra effort, the rigid train cannot efficiently simulate the flexible book for certain messy puzzles.

• Analogy: It's like having a Swiss Army Knife (flexible) vs. a rigid ruler (fixed order). Even if you tape a few extra tools to the ruler, it still can't cut a complex shape as well as the Swiss Army Knife can. The rigidity of the order is the bottleneck.

3. The "Apply" Operation (Merging Two Blueprints)

Imagine you have two blueprints for two different parts of a house, and you want to combine them into one blueprint for the whole house. This is called the Apply operation.

• The Problem: For the rigid blueprints, combining them is usually a disaster. It's like trying to merge two train tracks that were built on different schedules. The result is a tangled mess that is exponentially larger than the original tracks.
• The Solution (The "Irregularity Index"): The authors discovered a special case where merging does work efficiently. They introduced a concept called the Irregularity Index.
  • Analogy: Imagine the rigid train track is mostly straight, but has a few "wiggles" where it deviates from the perfect line. If the number of wiggles is small (low irregularity), you can merge the tracks easily. If the tracks are a chaotic zig-zag (high irregularity), merging them causes an explosion in size.
  • This gives engineers a new way to measure how "close" a complex model is to a simple, efficient one.

4. A New, Stronger Blueprint

Finally, the authors invented a new, slightly relaxed version of the rigid blueprint called Structured $\land$d-fbdd.

• The Analogy: Think of the original rigid blueprint as a strict teacher who demands you follow the rules perfectly. The new version is a lenient teacher. They still want you to follow a structure, but they allow you to hide some of the "smart gates" inside the decision nodes so they don't have to follow the strict order.
• The Result: This new model is surprisingly powerful. It can handle those "globally messy" puzzles (Incidence Treewidth) much better than the old rigid models. In fact, it can handle puzzles that become simple if you just remove a few "bad" rules.

Summary of the Takeaway

1. Rigidity is a weakness: If you force a computer to ask questions in a fixed order, it struggles immensely with puzzles where the rules are scattered globally.
2. Merging is hard: Combining two rigid models usually creates a monster, unless they are very similar to a simple, straight line (low irregularity).
3. Flexibility wins: The authors propose a new, slightly more flexible model that might be the key to solving these hard puzzles efficiently.

The Big Open Question:
The paper ends by asking: Is this new, lenient model the "Holy Grail" that can solve all these messy puzzles efficiently? They suspect the answer might be "no," but proving it is the next big challenge for the field.

Technical Summary

Here is a detailed technical summary of the paper "On complexity of restricted fragments of Decision DNNF" by Andrea Calì and Igor Razgon.

1. Problem Statement and Motivation

The paper addresses the parameterized complexity of representing Boolean functions, specifically Conjunctive Normal Forms (CNFs), using Decision DNNF (Decomposable Negation Normal Form), also referred to as $\land^d$-fbdd (Free Binary Decision Diagrams equipped with decomposable conjunction nodes).

• Context: Decision DNNF is a powerful knowledge compilation model. It is known that CNFs with bounded primal treewidth admit Fixed-Parameter Tractable (FPT) representations in Decision DNNF.
• The Open Question: The complexity of representing CNFs with bounded incidence treewidth in Decision DNNF remains an open problem. While other restrictions (like Sentential Decision Diagrams) admit FPT representations for bounded incidence treewidth, it is unknown if Decision DNNF does.
• Specific Focus: The authors investigate two specific restrictions of Decision DNNF to shed light on this problem:
  1. $\land^d$-OBDD: Decision DNNFs respecting a fixed linear variable ordering (equivalent to OBDDs with $\land^d$ nodes).
  2. Structured Decision DNNF: Models where $\land^d$ nodes respect a specific variable tree (vtree).

2. Methodology

The authors employ a combination of combinatorial lower-bound techniques and structural analysis:

• Fooling Set Methodology for $\land^d$-OBDD:
  • They generalize the standard "number of subfunctions" lower bound technique used for OBDDs.
  • They introduce a $\land^d$-fooling set: A set of assignments $F$ over a prefix of a variable ordering $\pi$.
  • Key Concept: For each assignment $g \in F$, they define an unbreakable set $UB(g)$ (a set of variables that cannot be split by the model's structure) and prove that distinct assignments in $F$ must lead to distinct nodes in the model. This establishes that $|B| \ge |F|$.
• Embeddability and Irregularity Index:
  • To analyze the Apply operation (conjunction of two models), they introduce the concept of embeddability into a linear order. A model is embeddable if its sub-structures align with intervals of the linear order.
  • They define the irregularity index ($ir_\pi(B)$), a parameter measuring how far a model deviates from being a standard OBDD (which has an index of 0).
• Graph-Theoretic Reductions:
  • They utilize graph parameters like Linear Special Induced Matching Width (lsim-width) and treewidth to construct hard instances (e.g., grid graphs) that force exponential blow-ups in specific models.

3. Key Contributions and Results

A. Lower Bounds for $\land^d$-OBDD

The authors prove that $\land^d$-OBDDs are inefficient for CNFs of bounded incidence treewidth:

• XP Lower Bound: They re-establish that representing CNFs of bounded incidence treewidth requires XP-sized (exponential in the parameter) $\land^d$-OBDDs. This contrasts with the FPT upper bound for primal treewidth.
• Separation Results:
  • FBDD vs. $\land^d$-OBDD: There exists a class of CNFs representable by polynomial-sized FBDDs but requiring exponential-sized $\land^d$-OBDDs.
  • $\land^d$-OBDD vs. OBDD: There exists a class of CNFs representable by polynomial-sized $\land^d$-OBDDs but requiring exponential-sized OBDDs.
  • Significance: This highlights a surprising gap: while $\land^d$-fbdd can be quasi-polynomially simulated by FBDD, the addition of a static variable ordering (making it an OBDD) drastically reduces its power compared to the unordered case.

B. Complexity of the Apply Operation

The paper investigates whether the conjunction (Apply) of two $\land^d$-OBDDs can be performed efficiently.

• General Case: The Apply operation can lead to an exponential blow-up. Even if two models respect the same order and are linear-sized, their conjunction (e.g., the full grid function) may require exponential size.
• Restricted Case (Embeddability):
  • If two models are embeddable into the same linear order $\pi$, the Apply operation is efficient.
  • Theorem: If $B_1$ and $B_2$ have irregularity indices $k_1$ and $k_2$, their conjunction can be represented as an OBDD of size $O(|B_1| \cdot |B_2|)^{O(k_1+k_2)}$.
  • This provides a new parameterized view on the efficiency of knowledge compilation operations.

C. Structured $\land^d$-fbdd

The authors introduce a relaxed version of structuredness called Structured $\land^d$-fbdd.

• Definition: Unlike standard Structured Decision DNNF (where all $\land^d$ nodes must respect a vtree), Structured $\land^d$-fbdd only requires the explicit $\land^d$ nodes in the model to respect a vtree. The $\land^d$ nodes "hidden" inside decision nodes are unconstrained.
• Power: This model is significantly more powerful than Structured Decision DNNF.
  • It admits FPT-sized representations for CNFs that can be turned into bounded primal treewidth by removing a constant number of clauses.
  • In contrast, Structured Decision DNNF requires XP size even for such instances if the constant number of clauses is just two long clauses.
• Open Question: It remains unknown whether Structured $\land^d$-fbdd admits FPT representations for general CNFs of bounded incidence treewidth.

4. Significance and Implications

1. Resolution of the "Primal vs. Incidence" Dilemma: The paper confirms that for $\land^d$-OBDDs, the distinction between primal and incidence treewidth is critical. Bounded incidence treewidth is strictly harder to handle than bounded primal treewidth in this model, suggesting that static variable orderings are a bottleneck for incidence treewidth.
2. Solver Design Implications: The results suggest that for solvers using component analysis with static variable orderings (traced by $\land^d$-OBDDs), the overhead of component analysis is highly worthwhile, as the static ordering alone cannot handle incidence treewidth efficiently.
3. New Research Directions:
   • Irregularity Index: The introduction of the irregularity index opens a new avenue for analyzing the "distance" between restricted models and standard OBDDs, potentially leading to efficient transformation algorithms.
   • Proof Complexity: The authors draw a parallel between $\land^d$-OBDD lower bounds and Oblivious Resolution proofs, posing open questions about the complexity of oblivious resolution parameterized by incidence treewidth.
   • Structuredness: The definition of Structured $\land^d$-fbdd provides a promising candidate for a model that might bridge the gap between tractable primal treewidth and the harder incidence treewidth cases.

5. Conclusion

The paper makes significant progress in understanding the limitations of Decision DNNF fragments. It proves that $\land^d$-OBDDs are inherently limited for bounded incidence treewidth (XP lower bound) but identifies Structured $\land^d$-fbdd as a potentially powerful alternative. Furthermore, it establishes a novel framework for analyzing the efficiency of the Apply operation via embeddability and irregularity indices, offering a nuanced view on how structural restrictions impact computational complexity in knowledge compilation.