TAOCP 7.1.4 Exercise 181

Section 7.1.4: Binary Decision Diagrams

Exercise 181. [M21] [M21] Let Lm,n be the leading bit function Z(m+n) m,n (x1, . . . , xm; y1, . . . , yn). Prove that Bmin(Lm,n) = O(2mn) when m ≤n.

Verified: no
Solve time: 4m53s

We restart from the correct structural model of the function and rebuild the argument in a way that does not rely on an incorrect “single-bit carry” abstraction.

Correct Solution

Interpret $L_{m,n}$ as the most significant bit of the integer

$$ Z_{m,n} = \sum_{i=1}^{m}\sum_{j=1}^{n} x_i y_j 2^{i+j-2}, $$

so $Z_{m,n}$ is the usual binary convolution of two bit-vectors, and $L_{m,n}$ extracts its leading bit. The goal is to bound the size of a reduced ordered BDD under some variable ordering by $O(mn)$ when $m \le n$.

We use a diagonal ordering: all variables are grouped by weight $i+j$, and diagonals are processed in increasing order of $t=i+j$, with arbitrary order inside each diagonal. Let $D_t$ denote the set of variables ${(x_i,y_j) : i+j=t}$. Each product $x_i y_j$ contributes to bit position $t-2$.

Algorithm Walkthrough

Fix a diagonal variable ordering that processes all variables in $D_2, D_3, \dots, D_{m+n}$ in increasing order of $t=i+j$, with arbitrary ordering inside each diagonal.
For each diagonal $t$, define the partial sum

$$ S_t = \sum_{i+j=t} x_i y_j. $$

Since $i \le m$, every diagonal contains at most $m$ terms, hence $0 \le S_t \le m$. 3. Define the accumulated carry $c_t$ entering diagonal $t$. This carry is an integer, not a bit. It represents all contributions propagated from lower diagonals after binary addition. 4. Show the invariant: for every $t$, the carry satisfies $0 \le c_t \le m$. 5. Show that the transition from diagonal $t$ to $t+1$ depends only on $S_t + c_t$, and produces a new carry

$$ c_{t+1} = \left\lfloor \frac{S_t + c_t}{2} \right\rfloor, $$

which preserves the bound $c_{t+1} \le m$. 6. Characterize BDD states: after processing all variables in diagonals up to $t$, the remaining function depends only on:

the current diagonal index $t$,
the current carry $c_t$,
and (if inside a diagonal) the partial sum already accumulated in $S_t$, which ranges in $[0,m]$.

Count the number of distinct states induced by this structure and conclude the $O(mn)$ bound.

Carry and diagonal structure

We first justify the carry bound rigorously.

Each diagonal contributes at most $m$ Boolean products, so

$$ 0 \le S_t \le m. $$

Assume inductively that $0 \le c_t \le m$. Then

$$ 0 \le S_t + c_t \le 2m. $$

Binary addition implies that the contribution to the next diagonal is

$$ c_{t+1} = \left\lfloor \frac{S_t + c_t}{2} \right\rfloor \le m, $$

so the invariant is preserved.

Thus every carry value throughout the computation lies in the finite set ${0,1,\dots,m}$.

Correct BDD state characterization

We now identify what an ordered BDD node represents.

Fix the diagonal ordering. At any point in the BDD traversal, we are either:

between diagonals, or
partway through processing a diagonal.

1. Between diagonals

If all variables in diagonals $< t$ are fixed, then the remaining function depends only on:

$$ (t, c_t). $$

No additional memory is needed because all earlier diagonals influence the future only through the accumulated carry $c_t$, and all remaining computation is symmetric within future diagonals.

Thus there are at most

$$ (m+n) \cdot (m+1) $$

such states.

2. Inside a diagonal

Within a diagonal $D_t$, suppose we have processed some subset of its variables. The only relevant information about the past is:

the current carry $c$,
the number of already chosen $x_i y_j = 1$ contributions in this diagonal, i.e. a partial sum $s \in {0,\dots,m}$.

Any two partial assignments in $D_t$ that yield the same pair $(c,s)$ induce identical residual functions over the remaining variables, because future computation depends only on the total contribution of this diagonal, not on which specific pairs produced it.

Hence, within each diagonal, the number of distinct BDD nodes is at most

$$ (m+1) \cdot (m+1). $$

Global counting

There are $O(m+n)$ diagonals. For each diagonal:

$O(m)$ possible carry values,
$O(m)$ possible partial sums.

Thus the number of distinct reachable BDD nodes is bounded by

$$ O((m+n)\cdot m). $$

Since $m \le n$, we obtain

$$ (m+n)m = O(nm + m^2) = O(mn). $$

Correctness of state compression

The key justification is that the function’s future behavior depends only on aggregated arithmetic data:

contributions of completed diagonals collapse into a single integer carry $c_t$,
within a diagonal, only the count of selected products matters because all variables in the same diagonal contribute at the same weight and are interchangeable with respect to future computation.

Thus no two distinct histories with identical $(t,c,s)$ can diverge on any remaining input, establishing that these parameters fully characterize BDD subfunctions.

Conclusion

Under a diagonal variable ordering, every ordered BDD node for $L_{m,n}$ is uniquely determined by:

a diagonal index $t$,
a carry value $c_t \in {0,\dots,m}$,
and a partial diagonal sum $s \in {0,\dots,m}$.

This yields $O((m+n)m) = O(mn)$ distinct nodes, proving

$$ B_{\min}(L_{m,n}) = O(mn). $$

The previous failure stemmed from incorrectly treating the carry as a single bit; the correct model uses an integer carry bounded by $m$, which still yields a linear-state machine per diagonal and preserves the $O(mn)$ bound.