TAOCP 7.1.4 Exercise 113
Let $F_4$ denote the set of Boolean functions of four variables.
Section 7.1.4: Binary Decision Diagrams
Exercise 113. [20] [20] Instead of having two sink nodes, one for each Boolean constant, we could have 216 sinks, one for each Boolean function of four variables. Then a BDD could stop four levels earlier, after branching on xn−4. Would this be a good idea?
Verified: no
Solve time: 4m53s
Solution
Let $F_4$ denote the set of Boolean functions of four variables. The proposal replaces the two sink nodes $\bot,\top$ with $2^{16}$ sink nodes, each representing an element of $F_4$. A BDD for a Boolean function $f(x_1,\dots,x_n)$ would then terminate at depth $n-4$, and the last four variables would be absorbed into a terminal representing the induced subfunction of $x_{n-3},x_{n-2},x_{n-1},x_n$.
Every node at level $n-4$ corresponds to a subfunction of four variables obtained by fixing values of $x_1,\dots,x_{n-4}$. Each such subfunction is a Boolean function of four variables, hence an element of $F_4$, so it can indeed be represented by one of the proposed terminals. This establishes that the representation is well-defined and complete.
The key issue is the effect of this change on structure, size, and manipulation of BDDs.
In the standard model, every subfunction on four variables is represented by a reduced ordered BDD whose size is bounded independently of $n$, and whose internal sharing structure reflects decompositions into beads at levels $n,n-1,\dots,n-4$. In the proposed model, all of this internal structure is collapsed into a single terminal label. Thus each occurrence of a four-variable subfunction eliminates all nodes below level $n-4$.
This reduction does not change the number of distinct functions representable at the terminal layer. There are exactly $2^{16}$ Boolean functions of four variables, so the terminal set is minimal if every such function is to be representable distinctly. Hence no further reduction of the terminal set is possible without losing representational completeness.
The ordering condition of BDDs remains valid because all branching still occurs only on variables $x_1,\dots,x_{n-4}$, and every arc continues to go from smaller to larger indices. The reduction condition on internal nodes also remains valid, since equality of terminals is well-defined by equality in $F_4$, and no internal node has identical LO and HI successors by the standard BDD reduction rule.
The main difficulty appears when considering operations on BDDs. In the ordinary setting, Boolean operations on sinks are trivial because $\bot$ and $\top$ form a two-element Boolean algebra. Here, each terminal represents a function $g \in F_4$, and Boolean operations require pointwise combination of such functions:
$$ (g \star h)(x_1,x_2,x_3,x_4) = g(x_1,x_2,x_3,x_4)\star h(x_1,x_2,x_3,x_4). $$
Thus every Boolean operation on BDDs induces an operation table of size $2^{16} \times 2^{16}$ at the terminal level. Even if this table is precomputed, the cost of storage and lookup is exponential in the terminal size, replacing a constant-time Boolean operation on ${\bot,\top}$ with a large combinatorial table indexed by truth tables of four variables.
The structural benefit is also limited. A standard BDD already represents each four-variable subfunction by a small canonical subgraph. Collapsing these subgraphs into terminals removes internal sharing among different occurrences of the same four-variable function only in a superficial sense, since terminals are atomic and shared automatically. However, it also destroys the internal decomposition that would otherwise be reused when those four-variable functions appear as parts of larger structured functions.
From an asymptotic viewpoint, the total size of a BDD for a function $f$ is reduced by at most the number of nodes in the last four levels of the diagram. This is bounded by a constant factor times the number of distinct four-variable subfunctions appearing in $f$. In exchange, each terminal carries a label of size $16$ bits of functional data, and operations on terminals require handling functions on four variables rather than single bits. This shifts complexity from graph size to algebraic complexity without improving worst-case growth rates.
The representation also loses conceptual uniformity. The classical BDD framework maintains a fixed Boolean algebra at the leaves, ensuring that all Boolean operations reduce to simple constant-time rules at terminals. Replacing this algebra with $F_4$ produces a much larger algebra in which the cost of terminal evaluation dominates the benefit of reduced depth.
Therefore the modification does not improve asymptotic efficiency of BDD representation or manipulation. It merely replaces four levels of graph structure by a large and operationally expensive terminal algebra, without reducing the inherent combinatorial complexity of Boolean functions.
This completes the proof. ∎