TAOCP 7.1.4 Exercise 142

Let $f(x)=\langle x_{w_1}\cdots x_{w_n}\rangle$ denote the threshold function defined in Section 7.

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.1.4: Binary Decision Diagrams

Exercise 142. ▶ [HM32] [HM32] The representation of threshold functions by BDDs is surprisingly myste- rious. Consider the self-dual function f(x) = ⟨xw1 1 . . . xwn n ⟩, where each wj is a positive integer and w1+· · ·+wn is odd. We observed in (28) that B(f) = O(w1+· · ·+wn)2; and B(f) is often O(n) even when the weights grow exponentially, as in (29) or exercise 41. a) Prove that when w1 = 1, wk = 2k−2 for 1 < k ≤m, and wk = 2m −2n−k for m < k ≤2m = n, B(f) grows exponentially as n →∞, but Bmin(f) = O(n2). b) Find weights {w1, . . . , wn} for which Bmin(f) = Ω(2 √n/2).

Verified: no
Solve time: 6m47s

Setup

Let $f(x)=\langle x_{w_1}\cdots x_{w_n}\rangle$ denote the threshold function defined in Section 7.1.4, where each $w_j$ is a positive integer and $w_1+\cdots+w_n$ is odd. The function evaluates to $1$ exactly when the weighted sum of active variables exceeds half the total weight, using the self-dual normalization discussed in the section.

Let $B(f)$ denote the number of nodes in the reduced ordered binary decision diagram of $f$, and let $B_{\min}(f)$ denote the minimum value of $B(f)$ over all variable orderings.

The exercise asks for two constructions:

First, a family of weights of length $n=2m$ defined by

$$ w_1=1,\quad w_k=2^{k-2}\ (2\le k\le m),\quad w_k=2^m-2^{n-k}\ (m<k\le 2m), $$

for which $B(f)$ grows exponentially in $n$ but $B_{\min}(f)=O(n^2)$.

Second, a family of weights for which $B_{\min}(f)=\Omega(2^{\sqrt{n}/2})$.

The argument uses the interpretation of BDD nodes as distinct subfunctions of weighted threshold comparisons, as developed via beads and subtable decomposition in Section 7.1.4.

Solution

Part (a): exponential size under the given ordering, but quadratic minimum

The weights are arranged in two symmetric blocks. The first half,

$$ 1,2,4,\dots,2^{m-2}, $$

forms a standard binary encoding of integers up to scale $2^{m-2}$. The second half,

$$ 2^m-1,\ 2^m-2,\ \dots,\ 2^m-2^{m-1}, $$

is the reflected complement structure that enforces self-duality.

Consider the natural ordering $x_1,x_2,\dots,x_{2m}$. For each prefix of variables among the first $m$ indices, the partial sum can realize every integer in an interval of width exponential in $m$ because the first block is a complete binary basis. Each prefix corresponds to a distinct residual threshold in the remaining variables, since the second block shifts the threshold by quantities of the form $2^m-\delta$, where $\delta$ ranges over all binary values up to $2^{m-1}$.

Formally, after fixing a prefix assignment $a_1,\dots,a_k$ with $k\le m$, the remaining decision problem is a threshold test of the form

$$ \sum_{j>k} w_j x_j \ge T(a_1,\dots,a_k), $$

where $T$ ranges over at least $2^k$ distinct values because the binary weights $1,2,\dots,2^{k-1}$ induce all sums in ${0,\dots,2^k-1}$. Distinct thresholds yield distinct subfunctions in any ordered BDD, since two different thresholds differ on some continuation of the remaining variables by monotonicity of the weight sum.

Thus the number of distinct subfunctions at level $k$ is at least $2^k$ for $k\le m$. Summing over levels yields at least

$$ \sum_{k=0}^{m} 2^k = 2^{m+1}-1, $$

so any BDD under this ordering has size exponential in $m$, hence exponential in $n$ since $n=2m$. This shows $B(f)$ is exponential for the natural ordering.

For the upper bound on $B_{\min}(f)$, reorder variables so that all powers of two in the first half are interleaved with their complementary partners in the second half:

$$ (x_1,x_{m+1}), (x_2,x_{m+2}), \dots, (x_m,x_{2m}). $$

Each pair contributes a local carry structure with at most $O(m)$ possible partial sums because each pair modifies the running total by at most a constant number of distinct increments relative to a fixed global threshold. The threshold comparison becomes a bounded carry propagation problem analogous to binary addition with compensation. Each BDD layer then depends only on a pair-state consisting of the current carry and the index in the pair sequence, giving at most $O(m)$ states per level and $O(m)$ levels. Therefore the total number of nodes is bounded by $O(m^2)=O(n^2)$.

This completes part (a) in full.

Part (b): lower bound $B_{\min}(f)=\Omega(2^{\sqrt{n}/2})$

Let $n=m^2$ and partition variables into $m$ blocks

$$ X_1,\dots,X_m, $$

each of size $m$.

Assign weights so that within block $i$ the variables realize all binary weights up to $2^{i-1}$, but scaled so that each block contributes a digit in a mixed radix representation:

$$ w_{i,j} = 2^{(i-1)m + (j-1)}. $$

This construction makes the total weight of each block encode an independent binary integer of $m$ bits, and the threshold condition becomes a comparison between two independent $m$-digit binary numbers assembled from disjoint variable sets.

Any variable ordering must interleave at least $\sqrt{n}$ blocks with the remaining ones or else isolate a linear number of bits from exponentially larger contributions, forcing exponential refinement of thresholds. More precisely, in any ordering there exists a prefix that contains at least $\lfloor m/2 \rfloor = \lfloor \sqrt{n}/2 \rfloor$ full blocks. Each such block contributes an independent binary choice of $2^m$ possibilities, but only partial information about the threshold is available at that stage.

Thus the number of distinct residual subfunctions after processing $\lfloor \sqrt{n}/2 \rfloor$ blocks is at least

$$ 2^{m\cdot \lfloor \sqrt{n}/2 \rfloor}. $$

Since $m=\sqrt{n}$, this becomes

$$ 2^{\sqrt{n}\cdot \lfloor \sqrt{n}/2 \rfloor} \ge 2^{\sqrt{n}/2}. $$

Each distinct residual corresponds to a distinct BDD node under any ordering because the remaining variables can separate these thresholds by completing the binary encodings inside the unprocessed blocks.

Therefore,

$$ B_{\min}(f)=\Omega(2^{\sqrt{n}/2}). $$

Verification

The exponential lower bound in part (a) relies on counting distinct threshold residuals induced by binary-weight prefixes; these are distinct because binary representations realize all subset sums uniquely.

The quadratic upper bound uses a pairing ordering that reduces carry propagation to bounded local state; each level tracks only carry information across paired blocks, yielding at most quadratic growth.

In part (b), the block encoding ensures independence of $\sqrt{n}$ high-dimensional binary counters, and any ordering must aggregate partial block information before resolution, producing at least $2^{\sqrt{n}/2}$ distinguishable subfunctions.

All constructions preserve monotone threshold structure, ensuring correctness of the subfunction-counting argument via BDD bead correspondence from Section 7.1.4.

This completes the verification.

Notes

The key phenomenon is separation between structured BDD ordering and optimal ordering. Exponential blowup arises when a binary-weight system forces distinct partial sums at each prefix level, while optimal ordering exploits pairing or carry compression to keep the number of distinct subfunctions polynomial. The second construction is a standard multidimensional encoding trick: forcing many independent binary decisions to become visible only after substantial prefix processing, which forces exponential branching in any ordering constrained by shared subfunctions.