A large normal form need not mean expensive future queries

Our broader goal is to understand future behavior represented by finite rules with bounded local access and allocation. For independently prepared constraints, must composition be expensive because a canonical representation becomes large? A classical example shows why the required output format must be separated from the queries we actually need.

The imported example

Van den Broeck and Darwiche’s On the Role of Canonicity in Knowledge Compilation (2015), full version, Appendix Theorems 5–6 and Figure 5a, supplies this family. Let $m\ge1$,

$$e_i(Y)=Y_i\land\bigwedge_{j<i}\neg Y_j,$$ $$f_m=\bigvee_{i=1}^m e_i(Y)\land[(X_i\land(W\lor Z_i))\lor(\neg X_i\land Z_i)].$$

A sentential decision diagram (SDD) represents a Boolean function using recursive variable partitions. Fix the variable tree with root split $(X,Y)\mid(Z,W)$ and left split $X\mid Y$. The operands $f_m$ and $W$ have polynomial-size compressed SDDs. Conjoining them forces a compressed-output prime

$$H_m(X,Y)=\bigvee_i e_i(Y)X_i.$$

All $2^m$ assignments to $X$ give distinct residual functions of $Y$: choose a first true $Y_i$ at a coordinate where two assignments differ. Consequently the compressed output contains at least $2^m$ elements. This is the authors’ fixed-variable-tree representation lower bound, not a lower bound for every representation of the function.

What the output bound charges

Here is the resource translation. Both fragments are prepared independently. The deterministic composer must return the explicit compressed SDD under that same tree. Each SDD element occupies an ordinary record; variable-length lists use additional bounded-arity records. A succinct program standing for many elements does not meet this output contract.

Let $S$ count all available records after preparation, including shared tables, old versions, and any prebuilt answers. Let $a$ be the fixed maximum number of records allocated per local step. If $T$ steps elapse before the required output exists, then

$$S+aT\ge 2^m.$$

Only $S$ old records and $aT$ fresh records can exist. This argument even allows arbitrary inspection of old storage; no communication simulation is needed. For polynomial $S$, it gives exponential post-preparation allocation and time. Any deferred construction remains charged until the explicit output is complete.

Declare the common query boundary to be $X\cup Y\cup Z\cup\{W\}$, with $b=3m+1$ variables. The second fragment constrains only $W$: the actual support intersection has size one, not $b$. To fix an input convention, write the displayed operands as ordinary expression trees, expanding each prefix $e_i$, with fixed-width binary variable names. Their combined description has $N=\Theta(m^2\log(m+2))$ bits, with no auxiliary variables or implicit tables. This is a native Boolean-formula input, not a CNF encoding claim. Thus the output requirement is exponential in the declared query width despite polynomial-size formulas. The input admits polynomial preparation into the stated SDDs; tighter shared encodings are unnecessary for this comparison.

Unrestricted stored preparation invalidates the claimed post-preparation conclusion. Since the partner here is the fixed literal $W$, preparation of $f_m$ can prebuild the large answer and retain its root. Returning that root can then be cheap. Its construction and storage have already been paid for. A bound on input size alone does not exclude this possibility.

The same function has an easy query procedure

Set $g_m=f_m\land W$. For any complete assignment, let $i$ be the first position with $Y_i=1$. Direct substitution gives

$$g_m=\begin{cases}W\land(X_i\lor Z_i),&\text{if such an }i\text{ exists},\\0,&\text{otherwise}.\end{cases}$$

Supply an assignment as $W$ followed by the ordered triples $(X_i,Y_i,Z_i)$. A finite-state scan remembers $W$, selects the first true $Y_i$, and retains one answer bit. It takes $O(b)$ local steps. An immutable implementation may allocate a cursor/state record per step, so the safe bound is $O(b)$ fresh records, with constant allocation per step. No pointer identity or address arithmetic is required. Reading and retaining the assignment, if necessary, is also charged $O(b)$ work.

Moreover, compatibility of these particular operands is always true: set $W=X_1=Y_1=1$. These facts concern the promised family, not arbitrary SDD operands or arbitrary later conjunctions. They show directly that its exponential canonical output is unnecessary for these semantic queries. Returning a lazy pair alone would not establish this; the explicit query procedure does.

Consequence for the research direction

The existing operational interface requires correct decoded behavior, not a unique physical graph. Therefore this canonical-output obstruction cannot serve as a general FPRD obstruction without an additional reason that the normal form is required. Nor does it settle the cost of changing variable trees or finding a better one.

This is an application of an imported theorem plus elementary allocation accounting and a written query procedure. It is independently reviewed, not formally verified, and makes no novelty claim. The useful next question is whether independent pieces need a shared variable order or decomposition to compose efficiently. That tests the structural agreement between fragments, rather than imposing canonicity by default.