TAOCP 7.1.4 Exercise 88

Section 7.1.4: Binary Decision Diagrams

Exercise 88. ▶ [M25] [M25] Find functions f, g, and h for which the recursive ternary computation of f ∧g ∧h outperforms any of the binary computations (f ∧g)∧h, (g ∧h)∧f, (h∧f)∧g.

Verified: no
Solve time: 8m42s

Solution

Let variables be ordered $x_1 < x_2 < \cdots < x_n$. The recursive BDD computation of a conjunction proceeds by Shannon expansion at the current variable and then combines cofactors. In a binary scheme, computing $(f \wedge g)$ first forms a BDD whose intermediate nodes are pairs of cofactors $(f_0,g_0)$ and $(f_1,g_1)$ before any interaction with $h$ is considered. In a ternary scheme, the recursion forms triples $(f_\alpha,g_\alpha,h_\alpha)$ at every expansion level, so that inconsistencies among the three functions can force immediate collapse of entire subgraphs before any pairwise product is materialized.

Take $n \ge 3$ and partition variables into three blocks

$$ X = (x_1,\dots,x_m), \quad Y = (x_{m+1},\dots,x_{2m}), \quad Z = (x_{2m+1},\dots,x_{3m}). $$

Define Boolean functions

$$ f(X,Y,Z) = \bigoplus_{i=1}^{m} x_i,\quad g(X,Y,Z) = \bigoplus_{i=1}^{m} x_{m+i},\quad h(X,Y,Z) = \bigoplus_{i=1}^{m} x_{2m+i}, $$

where $\oplus$ is exclusive-or.

Each function depends only on a disjoint block, and each has a BDD of size linear in $m$ under the fixed variable ordering, since evaluation follows a single path in each block without sharing between blocks.

Consider first any binary computation, for example $(f \wedge g) \wedge h$. The BDD for $f \wedge g$ is obtained by combining two parity subfunctions on disjoint variable blocks. At each level in block $X$, the construction must retain both parity states of $g$, and symmetrically in block $Y$ both parity states of $f$, because neither function determines the other. The resulting intermediate BDD for $f \wedge g$ therefore contains a Cartesian product of the two parity state spaces, producing $4$ distinct subfunctions at every depth where both parities remain unresolved. The subsequent conjunction with $h$ introduces a third independent parity state, so every binary parenthesization necessarily builds a product structure of size proportional to $2^{2m}$ at intermediate stages before reduction collapses terminal inconsistencies.

Now consider the ternary recursive computation of $f \wedge g \wedge h$. At the root, Shannon expansion on $x_1$ immediately fixes the parity state of $f$ at that level. In the same expansion step, neither $g$ nor $h$ depends on $x_1$, so the ternary state separates as

$$ (f_0,g,h), \quad (f_1,g,h). $$

As expansion proceeds through the block $X$, each assignment completely determines the value of $f$, so after processing the first block the recursion reaches states in which $f$ is a constant $0$ or $1$. In either case, the conjunction $f \wedge g \wedge h$ collapses immediately to $0$ without constructing any cross-product between the parity automata of $g$ and $h$.

The same collapse occurs symmetrically when $g$ or $h$ becomes determined in their respective blocks. Since the ternary recursion never forms an intermediate node representing a pair of unresolved parity states from different blocks, no product construction of the form $(f \wedge g)$, $(g \wedge h)$, or $(h \wedge f)$ is ever materialized inside the recursion.

The binary schemes are forced to combine two independent parity automata before the third constraint is introduced, producing intermediate BDDs whose number of beads grows multiplicatively with the sizes of the two participating functions. The ternary scheme introduces all three constraints simultaneously at every Shannon expansion level, so contradictions propagate immediately across blocks and eliminate entire subtrees before any pairwise product structure is created.

Thus these parity-on-disjoint-block functions satisfy the required property: every binary parenthesization creates an intermediate product BDD of quadratic size in the number of blocks, while the ternary recursive computation avoids this intermediate blow-up by preventing pairwise state formation and collapsing inconsistent triples during simultaneous expansion. ∎