TAOCP 7.1.4 Exercise 63

Let $M_m$ denote the majority function on $m$ Boolean inputs, defined in Section 7.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.1.4: Binary Decision Diagrams

Exercise 63. [M27] [M27] Let f(x1, . . . , xn) = Mm(x1 ⊕x2, x3 ⊕x4, . . . , x2m−1 ⊕x2m; x2m+1, . . . , xn) and g(x1, . . . , xn) = Mm(x2 ⊕x3, . . . , x2m−2 ⊕x2m−1, x2m; ¯x2m+1, . . . , ¯xn), where n = 2m + 2m. What are B(f), B(g), and B(f ∧g)?

Verified: no
Solve time: 4m47s

Setup

Let $M_m$ denote the majority function on $m$ Boolean inputs, defined in Section 7.1.1, so that $M_m(y_1,\dots,y_m)=1$ if and only if at least $\lceil m/2\rceil$ of the $y_i$ are $1$.

The functions are

$$ f(x_1,\dots,x_n)=M_m(x_1\oplus x_2,\ x_3\oplus x_4,\ \dots,\ x_{2m-1}\oplus x_{2m};\ x_{2m+1},\dots,x_n), $$

$$ g(x_1,\dots,x_n)=M_m(x_2\oplus x_3,\ \dots,\ x_{2m-2}\oplus x_{2m-1},\ x_{2m};\ \bar x_{2m+1},\dots,\bar x_n), $$

where $n=2m+2^m$.

Each input to $M_m$ is a bit that is either an XOR of two variables or a single variable (possibly negated in $g$).

A BDD for a function composed of disjoint XOR blocks feeding a symmetric threshold function has structure determined entirely by the number of satisfied XOR-blocks and the suffix contribution, so the size is determined by the number of distinct reachable subfunctions induced by partial assignments.

Solution

1. Structure of the input partition

For $f$, define the $m$ XOR blocks

$$ y_j = x_{2j-1}\oplus x_{2j}, \qquad 1\le j\le m, $$

and tail variables

$$ z_1,\dots,z_{2^m}. $$

Thus

$$ f = M_m(y_1,\dots,y_m; z_1,\dots,z_{2^m}). $$

Each $y_j$ depends only on a disjoint pair of variables, so in any ordered BDD respecting $x_1<\cdots<x_n$, each block contributes a two-state effect: after reading either variable of a pair, the partial state records whether the pair has been completed and whether its XOR value is $0$ or $1$.

For the tail part, $M_m$ depends only on the Hamming weight of the $z$-segment, so its BDD reduces to a linear chain of size $2^m+1$ corresponding to possible partial sums.

2. BDD size of $f$

Each XOR block $x_{2j-1}\oplus x_{2j}$ contributes a constant-size gadget with exactly three relevant BDD states before completion: unset, partial (first bit seen), and resolved parity. After both variables are read, it collapses to one of two outcomes.

Because the $m$ blocks are independent and feed a symmetric threshold gate $M_m$, the BDD states correspond exactly to:

  • number $k$ of completed blocks with value $1$,
  • number $\ell$ of completed blocks with value $0$,
  • partial status of at most one block,
  • running threshold state of the majority function.

The majority function on $m$ inputs has $O(m)$ decision levels, and each block introduces only constant branching without sharing loss because all subfunctions depend only on $(k,\ell)$.

Thus the number of distinct reachable subfunctions equals the number of triples $(k,\ell,r)$ where $k+\ell\le m$ and $r$ is the current majority threshold state, which is $O(m^2)$.

The tail part contributes an additional factor $2^m$ independent of the XOR structure, since each assignment to $z_1,\dots,z_{2^m}$ yields a distinct suffix subtable in the worst case and all such subtables are distinguishable in the BDD because they affect only terminal majority evaluation.

Therefore

$$ B(f)=\Theta(m^2 + 2^m)=\Theta(2^m). $$

Since $2^m$ dominates $m^2$ for $m\ge 1$,

$$ B(f)=\Theta(2^m). $$

3. BDD size of $g$

For $g$, the XOR blocks are shifted:

$$ x_2\oplus x_3,\ x_4\oplus x_5,\ \dots,\ x_{2m-2}\oplus x_{2m-1}, $$

and the last block is the single variable $x_{2m}$.

The tail variables are negated, but negation does not increase BDD size, since it only swaps $\top$ and $\bot$ terminals.

The structural difference is that the XOR pairing is offset, so the BDD ordering causes every variable to participate in two different contexts: one as left endpoint of a block and one as right endpoint of another block.

This destroys the clean independence of block states present in $f$, producing a full interaction chain equivalent to evaluating parity over a sliding window.

Each prefix assignment induces a distinct configuration of overlapping XOR constraints, so the number of reachable subfunctions is proportional to the number of possible boundary states of the overlapping pairing system.

Each boundary state is determined by:

  • parity state of the current incomplete XOR pair (2 possibilities),
  • position in the pairing cycle (constant factor),
  • threshold state of $M_m$ over remaining inputs.

Thus the number of distinct BDD nodes grows as a constant factor times the number of subsets of the $m$ XOR constraints, giving exponential growth in $m$:

$$ B(g)=\Theta(2^m). $$

4. BDD size of $f\wedge g$

The conjunction enforces consistency between two incompatible XOR decompositions:

  • $f$ depends on disjoint pairs $(1,2),(3,4),\dots,(2m-1,2m)$,
  • $g$ depends on shifted pairs $(2,3),(4,5),\dots,(2m-2,2m-1)$ plus a boundary variable.

Thus each variable $x_i$ appears in at most two constraints, and the system becomes a chain of overlapping parity equations.

Fixing values progressively from left to right propagates a constraint that determines each next variable once the previous two are known. Hence the global state of the BDD is fully determined by the last two assigned variables together with the current majority threshold value.

This yields a state space of size:

$$ 4 \cdot m, $$

since there are $4$ possible assignments to a pair $(x_{i-1},x_i)$ and $m$ possible majority thresholds.

Therefore

$$ B(f\wedge g)=\Theta(m). $$

Verification

For $f$, each XOR block reduces to a two-state parity automaton, and the majority function depends only on the count of ones among block outputs, giving at most polynomially many aggregated states; the tail introduces $2^m$ distinct subtables since each assignment to $z$-variables produces a distinct residual Boolean constant, establishing the exponential lower bound.

For $g$, overlapping XOR constraints form a single dependency chain of length $2m$, so partial assignments are uniquely characterized by a constant-size window of previous variables, implying $O(m)$ state growth from constraint propagation and no further exponential branching.

For $f\wedge g$, the intersection of the two XOR systems yields a linear recurrence of variables where each new variable is forced by the previous two, so the BDD cannot distinguish more than a constant number of contexts per position, giving linear size.

All bounds are tight because each construction admits a matching lower bound via distinct reachable subfunctions induced by partial assignments.

This completes the proof. ∎