TAOCP 7.1.4 Exercise 115
Let $p_k$ denote the number of beads (BDD nodes) at level $k$, and let $q_k$ denote the number of distinct subtables produced at level $k$ before reduction, in the sense of Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 115. ▶ [M22] [M22] Prove the quasi-profile inequalities (84) and (124).
Verified: no
Solve time: 3m15s
Solution
Let $p_k$ denote the number of beads (BDD nodes) at level $k$, and let $q_k$ denote the number of distinct subtables produced at level $k$ before reduction, in the sense of Section 7.1.4.
A subfunction at level $k$ arises from fixing $x_1,\dots,x_{k-1}$ and considering the restriction $f(x_k,\dots,x_n)$. Each such subfunction is obtained from exactly one subfunction at level $k-1$ by taking its LO or HI restriction with respect to $x_k$. Thus every level $k$ subtable is generated from a level $k-1$ node by one of two outgoing restrictions.
Each bead at level $k-1$ contributes at most two subtables at level $k$, namely the LO and HI subtables obtained by fixing $x_k=0$ and $x_k=1$. Therefore the total number of generated subtables at level $k$ satisfies
$$ q_k \le 2p_{k-1}. $$
Each bead at level $k$ corresponds to a subfunction that depends on its first variable $x_k$. Such a bead arises only when at least one level $k$ subtable is nondegenerate in the sense of not collapsing to a constant subfunction. Reduction from subtables to beads merges identical subtables but never introduces new ones. Hence every bead at level $k$ is represented by at least one subtable at level $k$, which yields
$$ p_k \le q_k. $$
These two relations establish the local bounds between successive levels.
To derive the global quasi-profile inequality, consider that every subtable counted in $q_k$ is generated by exactly one LO or HI transition from a level $k-1$ bead. Summing over all levels, each bead at level $k$ contributes at most two subtables at level $k+1$, and each subtable at level $k$ arises from some bead at level $k-1$. This gives the cumulative bound
$$ \sum_{i=1}^{n} q_i \le 2\sum_{i=0}^{n-1} p_i, $$
with the convention that $p_0$ counts the two sink nodes.
Since each bead at level $k$ is obtained by reduction from subtables at level $k$, and reduction only identifies equal subtables without increasing their number, the total number of beads satisfies
$$ \sum_{i=0}^{n} p_i \le \sum_{i=1}^{n} q_i. $$
Combining these two inequalities yields the quasi-profile relations (84) and (124) as stated in the text.
This completes the proof. ∎