TAOCP 7.1.4 Exercise 185

Section 7.1.4: Binary Decision Diagrams

Exercise 185. [M25] [M25] How large can Z(f) be, when f is a symmetric Boolean function of n variables? (See exercise 44.)

Verified: no
Solve time: 3m08s

Solution

Let $f(x_1,\dots,x_n)$ be symmetric, so its value depends only on the Hamming weight $$ w = x_1 + \cdots + x_n. $$ Hence there exist values $f_0,f_1,\dots,f_n \in {0,1}$ such that $f(x)=f_w$ whenever $|x|=w$.

We study the size of the ZDD representation $Z(f)$, i.e. the number of ZDD nodes in the reduced ordered structure that enumerates the satisfying assignments of $f$ in subset form.

A ZDD differs from a BDD in that a node with low edge corresponding to exclusion and high edge corresponding to inclusion is reduced by eliminating nodes whose high child is $\perp$, and merging is based on identical $(\mathrm{var}, \mathrm{lo}, \mathrm{hi})$ triples under the ZDD reduction rules. The crucial structural difference is that ZDD size is governed by how many distinct residual families remain when variables are processed in order.

For a symmetric function, after fixing the first $k$ variables, only the number of ones chosen among them matters. Thus every subproblem is determined entirely by a pair $(k,t)$ where $t$ is the number of ones selected so far. The remaining condition depends only on whether there exists an extension of size $n-k$ that reaches a weight $w$ with $f_w=1$.

Define $$ S_k(t) = { A \subseteq {x_{k+1},\dots,x_n} : |A| + t \in W }, $$ where $W = { w : f_w = 1 }$.

Then all states at level $k$ in the ZDD correspond to distinct shifted sets of admissible remaining weights $$ W - t = { w-t : w \in W, w \ge t }. $$ Two states $(k,t)$ and $(k,t')$ induce identical sub-ZDDs exactly when the truncated sets $W-t$ and $W-t'$ coincide.

Thus the number of distinct nodes at level $k$ is the number of distinct truncations of $W$ by shifts in $t$.

We now bound how many distinct such shifts can exist.

The set $W$ is a subset of ${0,1,\dots,n}$ and is monotone only in the sense of being ordered; symmetry imposes no monotonicity, so $W$ may be arbitrary.

For each shift $t$, the set $W-t$ is determined by translating $W$ and removing all elements below zero. The structure of $W-t$ changes only when $t$ crosses a boundary between consecutive elements of $W$ or between consecutive gaps in $W$.

Let $W = {w_1 < w_2 < \cdots < w_r}$. The shifted set $W-t$ changes only when $t$ passes one of the values in $$ {w_i} \cup {w_i - 1}. $$ Hence there are at most $2r+1$ distinct shifted forms. Since $r \le n+1$, this gives the crude upper bound $$ Z(f) \le O(n). $$

This bound is not tight for ZDDs because ZDD nodes correspond not only to shifts of $W$ but to residual families of subsets, and merging occurs whenever the continuation behavior over all suffix variables coincides. For symmetric functions, the ZDD construction is equivalent to a layered automaton over counts $t$ with acceptance determined by whether $t + u \in W$.

Thus the ZDD is equivalent to a deterministic acyclic automaton whose states correspond exactly to reachable values of $t$ together with equivalence classes induced by future acceptance conditions.

Two different $t$ and $t'$ are distinguishable if there exists $u$ such that $$ (t+u \in W) \ne (t'+u \in W). $$

This is equivalent to the condition that the indicator sequence of $W$ shifted by $t$ differs from that shifted by $t'$ at some coordinate. Hence the number of distinct states is exactly the number of distinct suffix patterns of the binary string $$ (f_0,f_1,\dots,f_n) $$ under shifts.

This is precisely the number of distinct substrings of a binary string, which is maximized when the string alternates as much as possible, i.e. when it has form $$ 010101\cdots \quad \text{or} \quad 101010\cdots $$ up to endpoints.

A binary string of length $n+1$ has at most $$ \frac{(n+1)(n+2)}{2} $$ distinct substrings, and this bound is tight for alternating strings.

Therefore the ZDD size satisfies $$ Z(f) \le \frac{(n+1)(n+2)}{2}. $$

To show tightness, consider the symmetric function defined by $$ f_w = 1 \iff w \text{ is even}. $$ Then the sequence is alternating. Each shift produces a distinct parity pattern on suffixes, yielding all substrings as distinct residual behaviors. This realizes $\Theta(n^2)$ distinct ZDD nodes.

Finally, no symmetric function can exceed this bound because any ZDD state is determined entirely by the pair consisting of current index and residual acceptance pattern, and the number of such patterns is bounded by the number of distinct substrings of the defining acceptance sequence.

Thus the maximal ZDD size for a symmetric Boolean function is quadratic in $n$.

This completes the proof. ∎