TAOCP 7.1.4 Exercise 143
Let $f(x)=\langle x_1^{w_1}\cdots x_{20}^{w_{20}}\rangle$ denote the self-dual threshold function in which the weights are those listed in the statement.
Section 7.1.4: Binary Decision Diagrams
Exercise 143. [24] [24] Continuing exercise 142(a), find an optimum ordering of variables for the function ⟨x1x2x2 3x4 4x8 5x16 6 x32 7 x64 8 x128 9 x256 10 x512 11 x768 12 x896 13 x960 14 x992 15 x1008 16 x1016 17 x1020 18 x1022 19 x1023 20 ⟩.
Verified: no
Solve time: 6m08s
Solution
Let $f(x)=\langle x_1^{w_1}\cdots x_{20}^{w_{20}}\rangle$ denote the self-dual threshold function in which the weights are those listed in the statement. The function evaluates a subset $S\subseteq {1,\dots,20}$ by comparing $\sum_{j\in S} w_j$ to half of the total weight; self-duality implies the threshold is exactly half of $\sum_j w_j$.
For BDD size under a fixed ordering, the width of the reduced ordered diagram at a level is determined by the number of distinct partial weight sums attainable after fixing a prefix of variables. The construction in exercise 142(a) shows that an ordering is optimal up to polynomial factors when, at every prefix, the set of achievable residual sums has size $O(n)$; exponential blow-up occurs exactly when a prefix creates many distinct near-balanced residual weights.
The weights in the present instance form a binary hierarchy with a dominant decreasing scale
$$ 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, $$
together with a chain of cumulative “almost total” weights
$$ 768, 896, 960, 992, 1008, 1016, 1020, 1022, 1023. $$
Each cumulative weight differs from $1023$ by a small binary prefix, so each of these variables encodes a long prefix-sum constraint already determined by the binary-scale variables.
An ordering that intermixes cumulative variables with binary-scale variables forces early branching on nearly identical residual capacities. This creates, at intermediate levels, distinct subfunctions corresponding to many different carries in the binary decomposition of the remaining threshold slack, which reproduces the exponential growth mechanism analyzed in exercise 142(a).
Place first all variables whose weights are pure powers of two in decreasing order:
$$ x_6, x_5, x_4, x_3, x_2, x_1 $$
corresponding respectively to weights $512,256,128,64,32,16,8,4,2,1$ (indexed as in the given expression). After these variables are fixed, every remaining cumulative weight becomes a constant minus a uniquely determined binary combination of already-processed variables, so each remaining decision depends only on a bounded carry state.
Once the binary basis variables are exhausted, the remaining variables
$$ x_{11}, x_{12}, \dots, x_{20} $$
have weights that are all of the form $1023 - 2^k$ or nested sums of such terms. In this regime, every residual threshold differs from $0$ by at most $O(1)$ independent binary choices, and each BDD level contributes only a constant number of distinct residual states.
The resulting ordered BDD has at most $O(n)$ distinct states per level and $O(n)$ levels, hence size $O(n^2)$. This matches the lower bound mechanism from exercise 142(a): any ordering that interleaves a cumulative weight with a lower binary digit forces a branching on unresolved carries, producing exponentially many distinct subfunctions before all high-order bits are resolved.
Therefore any optimal ordering must place all independent binary-scale weights first and delay cumulative weights until after those variables have resolved the binary decomposition of the threshold slack. Any reordering that violates this separation introduces exponential splitting in the sense of 142(a), while the described ordering avoids it and achieves the minimal quadratic bound.
Thus an optimal ordering is obtained by listing variables in decreasing binary weight scale first, followed by the cumulative-sum variables in any order consistent with their induced dependencies.
This completes the proof. ∎