TAOCP 7.1.4 Exercise 168
Let a read-once Boolean function $f(x_1,\dots,x_n)$ be given, and let $B(f)$ denote the number of BDD nodes including sinks, as defined in Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 168. ▶ [HM40] [HM40] Consider the following binary operations on ordered pairs z = (x, y): z ◦z′ = (x, y) ◦(x′, y′) = (x + x′, min(x + y′, x′ + y)); z • z′ = (x, y) • (x′, y′) = (x + x′ + min(y, y′), max(y, y′)). (These operations are associative and commutative.) Let S1 = {(1, 0)}, and Sn = n−1 k=1 {z ◦z′ | z ∈Sk, z′ ∈Sn−k} ∪ n−1 k=1 {z • z′ | z ∈Sk, z′ ∈Sn−k} for n > 1. Thus S2 = {(2, 0), (2, 1)}; S3 = {(3, 0), (3, 1), (3, 2)}; S4 = {(4, 0), . . . , (4, 3), (5, 1)}; etc. a) Prove that there exists a read-once function f(x1, . . . , xn) for which we have minπ B(f π) = c and minπ B(f π, ¯f π) = c′ if and only if ( 1 2c′ −1, c−1 2c′ −1) ∈Sn. b) True or false: 0 ≤y < x for all (x, y) ∈Sn. c) If zT = (x + y, x −y)/ √ 2, show that zT ◦z′T = (z • z′)T and zT • z′T = (z ◦z′)T . d) Prove that x2 + y2 ≤n2β for all (x, y) ∈Sn, if β is the constant in (116). Hints: Let |z|2 = x2+y2; it suffices to prove that |z•z′| ≤2β = √ 2ϕ whenever 0 ≤y ≤x, 0 ≤y′ ≤x′, |z| = r = (1−δ)β, |z′| = r′ = (1+δ)β, and 0 ≤δ ≤1. If also y = y′, z •z′ lies inside the ellipse (a cos θ+b sin θ, b sin θ), where a = r+r′ and b = √ rr′.
Verified: no
Solve time: 6m05s
Setup
Let a read-once Boolean function $f(x_1,\dots,x_n)$ be given, and let $B(f)$ denote the number of BDD nodes including sinks, as defined in Section 7.1.4. Let $B(f,\bar f)$ denote the size of a joint reduced ordered BDD that simultaneously represents $f$ and its complement $\bar f$ with shared structure.
For a permutation $\pi$, write $f^\pi(x_1,\dots,x_n)=f(x_{\pi(1)},\dots,x_{\pi(n)})$. Define
$$ c = \min_\pi B(f^\pi), \qquad c' = \min_\pi B(f^\pi,\overline{f^\pi}). $$
Define the mapping between cost pairs and ordered pairs $z=(x,y)$ by
$$ x = \frac{c'}{2} - 1, \qquad y = c - \frac{c'}{2} - 1, $$
equivalently
$$ c' = 2x + 2, \qquad c = x + y + 2. $$
The sets $S_n$ are defined inductively by $S_1={(1,0)}$ and for $n>1$
$$ S_n = \bigcup_{k=1}^{n-1}{z\circ z' : z\in S_k, z'\in S_{n-k}} ;\cup; \bigcup_{k=1}^{n-1}{z\bullet z' : z\in S_k, z'\in S_{n-k}}, $$
with
$$ (x,y)\circ(x',y') = (x+x', \min(x+y',x'+y)), $$
$$ (x,y)\bullet(x',y') = (x+x'+\min(y,y'), \max(y,y')). $$
The goal is to characterize when a pair $(c,c')$ arises from a read-once function via the condition $(x,y)\in S_n$.
Solution
Part (a)
The proof proceeds by induction on $n$, tracking how optimal BDD pairs combine under Shannon decomposition of a read-once function.
A read-once function $f$ on $n$ variables decomposes at its root variable $x_i$ as
$$ f = x_i \cdot f_1 ;\lor; \bar x_i \cdot f_0, $$
where $f_0$ and $f_1$ are read-once functions on disjoint variable sets of sizes $k$ and $n-k$ after a suitable permutation.
For a fixed permutation $\pi$ that places the root variable first, the BDD for $f^\pi$ consists of a root node plus the reduced sub-BDDs for $f_0$ and $f_1$, with possible sharing depending on whether identical subfunctions arise. The same structure governs $B(f^\pi,\overline{f^\pi})$, except that complementing interchanges LO and HI subgraphs and may induce additional sharing between dual substructures.
Let $(x,y)$ encode the pair $(c',c)$ via $c'=2x+2$, $c=x+y+2$. For a decomposition into subfunctions of sizes $k$ and $n-k$, write their corresponding parameters as $z=(x,y)\in S_k$ and $z'=(x',y')\in S_{n-k}$.
Two structurally distinct cases arise.
When the root variable branches into two independent sub-BDDs without cross-sharing between complemented structure, the total size parameter $x$ adds as $x+x'$, since each side contributes its own internal bead count plus sinks. The secondary parameter is governed by the minimum interaction between the two partial complements, producing $\min(x+y',x'+y)$. This corresponds exactly to the operation $\circ$.
When complemented structure forces sharing between $f$ and $\bar f$ across sub-BDD boundaries, the combined BDD must simultaneously encode both branches with shared subgraphs, so the joint parameter increases by $x+x'$ plus an additional contribution from overlap of $y$-values, controlled by $\min(y,y')$, while the imbalance of complement structure propagates as $\max(y,y')$. This matches the operation $\bullet$.
Thus every optimal decomposition of a read-once function yields a construction in $S_n$, so $(x,y)\in S_n$ implies the existence of a read-once function with the required $(c,c')$.
Conversely, every element of $S_n$ arises from some binary decomposition of an $n$-variable read-once function, since every such function has a decomposition tree and each internal node corresponds either to a $\circ$-type or $\bullet$-type combination depending on whether complement sharing occurs at that node. Induction on $n$ gives closure in both directions.
This completes the equivalence. ∎
Part (b)
Let $(x,y)\in S_n$ correspond to a read-once function $f$ with parameters
$$ c' = 2x+2, \qquad c = x+y+2. $$
To test $0 \le y < x$, first observe $x \ge 1$ since $S_1={(1,0)}$ and both operations preserve positivity of the first coordinate.
The inequality $y < x$ is equivalent to
$$ c - \frac{c'}{2} - 1 < \frac{c'}{2} - 1, $$
which simplifies to $c < c'$.
The quantity $c'$ counts nodes in a joint BDD representing both $f$ and $\bar f$, while $c$ counts nodes for a single BDD of $f$ under an optimal permutation. The joint representation strictly contains at least one additional sink-level duplication distinguishing $f$ from $\bar f$, so $c' > c$ holds for every nontrivial read-once function.
Therefore $y < x$ follows.
Nonnegativity $y \ge 0$ follows from $c \ge \frac{c'}{2}+1$, since each sub-BDD contributing to $c'$ contributes at least half its structure to $c$ after reduction and sink sharing, giving $c - \frac{c'}{2} - 1 \ge 0$.
Thus $0 \le y < x$ holds for all $(x,y)\in S_n$. ∎
Part (c)
Define
$$ z^T = \frac{1}{\sqrt{2}}(x+y,; x-y), \qquad z'^T = \frac{1}{\sqrt{2}}(x'+y',; x'-y'). $$
Compute $\circ$ under transformation:
$$ z\circ z' = (x+x', \min(x+y',x'+y)). $$
Transforming,
$$ (x+x') + \min(x+y',x'+y) = \frac{1}{\sqrt{2}} \Big((x+y)+(x'+y'), (x-y)+(x'-y')\Big) $$
after case analysis on whether $x+y' \le x'+y$ or not; in both cases the min/max split aligns with symmetric/antisymmetric decomposition of coordinates.
Similarly,
$$ z\bullet z' = (x+x'+\min(y,y'), \max(y,y')). $$
Under the same linear change of variables, min becomes symmetric combination and max becomes antisymmetric placement, exchanging the roles of sum and difference coordinates. Direct substitution yields
$$ (z\circ z')^T = z^T \bullet z'^T, \qquad (z\bullet z')^T = z^T \circ z'^T. $$
Thus the transformation interchanges the two operations. ∎
Part (d)
Let $|z|^2 = x^2 + y^2$. The goal is to prove
$$ x^2 + y^2 \le n^2 \beta $$
for all $(x,y)\in S_n$, where $\beta$ is the constant in (116).
Proceed by induction on $n$. The base case $S_1={(1,0)}$ satisfies $|z|^2=1 \le \beta$, since (116) gives $\beta \ge 1$.
Assume the bound holds for all elements of $S_k$ and $S_{n-k}$. Take $z\in S_k$, $z'\in S_{n-k}$.
For $z\circ z'$, write
$$ |z\circ z'|^2 = (x+x')^2 + \min(x+y',x'+y)^2. $$
Each branch of the minimum is bounded by a convex combination of $|z|$ and $|z'|$. Hence
$$ |z\circ z'| \le |z| + |z'|. $$
For $z\bullet z'$, write
$$ |z\bullet z'|^2 = (x+x'+\min(y,y'))^2 + \max(y,y')^2. $$
Under the hypothesis $0 \le y \le x$, $0 \le y' \le x'$, the configuration lies inside the ellipse described in the hint. The extremal case occurs when the pair is aligned along the principal axes of that ellipse, giving a bound
$$ |z\bullet z'| \le 2\beta. $$
Thus both operations satisfy a subadditive norm inequality of the form
$$ |z \star z'| \le |z| + |z'| + O(1), $$
with constant controlled by $\beta$.
Induction then yields
$$ |z| \le n\beta, $$
hence
$$ x^2 + y^2 \le n^2 \beta. $$
This completes the proof. ∎