TAOCP 7.1.4 Exercise 196

Exercise 196. [M21] [M21] Find a function f(x1, . . . , xn) for which Z(f) = O(n) and Z( ¯f) = Ω(n2).

Verified: no
Solve time: 1m42s

Solution

Let variables $x_1,\dots,x_n$ be interpreted as characteristic bits of a subset $S \subseteq {1,\dots,n}$, where $x_i=1$ means $i \in S$. In a zero-suppressed decision diagram (ZDD), the size $Z(f)$ counts nodes in the reduced diagram obtained under the zero-suppression rule described in Section 7.1.4, where subfunctions that force all remaining variables to $0$ are eliminated, and isomorphism merging is applied to identical subfunctions.

Define the Boolean function $f(x_1,\dots,x_n)$ to represent the family of subsets of size at most $1$. Equivalently,

$$ f = \left( \sum_{i=1}^n x_i \le 1 \right). $$

The complement $\overline{f}$ represents all subsets of size at least $2$, that is,

$$ \overline{f} = \left( \sum_{i=1}^n x_i \ge 2 \right). $$

We first analyze $Z(f)$. At any variable $x_i$, the remaining condition depends only on whether a single $1$ has already appeared. Thus the ZDD construction needs only two semantic states: “no $1$ seen yet” and “one $1$ already used.” Once a second $1$ would be introduced, the path is rejected immediately. Because of zero suppression, paths that skip variables do not introduce new distinct nodes beyond those indexed by the first occurrence of a $1$. Each level contributes at most a constant number of distinct nodes, and the diagram forms a linear chain over the variables. Therefore,

$$ Z(f) = O(n). $$

We now analyze $Z(\overline{f})$. The function $\overline{f}$ requires that at least two indices $i<j$ satisfy $x_i=x_j=1$. In a ZDD, a node must encode which variables are still available for selecting the second $1$ after the first $1$ has been placed.

Consider the state of the computation after the first $1$ is chosen at position $i$. From that point, the diagram must distinguish all possible choices of the second $1$ at positions $j>i$. For each fixed pair $(i,j)$ with $1 \le i < j \le n$, the ZDD contains a distinct substructure representing the residual condition “no second $1$ chosen before $j$, and the second $1$ placed at $j$”. These substructures are pairwise non-isomorphic because the earliest forced choice point differs: the position $j$ at which acceptance occurs is part of the residual constraint and cannot be merged under reduction.

Thus the ZDD contains at least one distinct configuration for each ordered pair $(i,j)$ with $i<j$. The number of such pairs is

$$ \sum_{i=1}^{n-1} (n-i) = \frac{n(n-1)}{2}. $$

Hence,

$$ Z(\overline{f}) = \Omega(n^2). $$

Combining both bounds, the function $f$ satisfies

$$ Z(f)=O(n), \qquad Z(\overline{f})=\Omega(n^2). $$

This completes the proof. ∎