TAOCP 7.1.2 Exercise 18
Let $C_m(f)$ denote the minimum-memory complexity of a Boolean function $f(x_1,\ldots,x_5)$, defined as the least number of working registers required in a straight-line Boolean chain in which each st...
Section 7.1.2: Boolean Evaluation
Exercise 18. ▶ [35] [35] Investigate optimum minimum-memory computations for $f(x_1, x_2, x_3, x_4, x_5)$: How many classes of five-variable functions have $C_m(f) = r$, for $r = 0, 1, 2, \ldots$?
Verified: no
Solve time: 2m46s
Setup
Let $C_m(f)$ denote the minimum-memory complexity of a Boolean function $f(x_1,\ldots,x_5)$, defined as the least number of working registers required in a straight-line Boolean chain in which each step has the form
$x_k \leftarrow x_i \circ x_j,\qquad 0 \le i,j < k,$
with reuse of registers allowed as in Section 7.1.2.
Two functions are in the same class for a given value of $C_m$ when they are identical as truth tables; the “classes” in the table therefore correspond to equivalence classes under equality of functions on ${0,1}^5$.
The task is to determine, for each $r \ge 0$, how many distinct Boolean functions of five variables satisfy
$C_m(f) = r.$
Let $N_r^{(5)}$ denote this number.
Solution
Each Boolean function on five variables depends on at most five essential variables. For each $k \in {0,1,2,3,4,5}$, let $f$ be a function whose set of essential variables has cardinality $k$. Such a function is uniquely determined by a Boolean function of $k$ variables together with a choice of which $k$ variables among $x_1,\ldots,x_5$ are essential.
There are $\binom{5}{k}$ ways to choose the essential variable set.
Let $N_r^{(k)}$ denote the number of $k$-variable Boolean functions with $C_m(f)=r$, computed in the sense of Section 7.1.2 for $k$ variables. Then each $k$-variable function yields exactly $\binom{5}{k}$ distinct five-variable functions with the same minimum-memory complexity, since adding inessential variables does not change any register computation.
Hence
$N_r^{(5)} = \sum_{k=0}^5 \binom{5}{k} N_r^{(k)}.$
The values $N_r^{(k)}$ for $k \le 4$ are determined by the exhaustive computations summarized in Table 1 of Section 7.1.2, since minimum-memory evaluation coincides with the computed complexity classes for all functions of at most four variables.
For $k=0$, the only functions are the constants $0$ and $1$, so
$N_0^{(0)} = 2,\qquad N_r^{(0)} = 0 \text{ for } r \ge 1.$
For $k=1$, the functions are constant or projection, so only $r=0,1$ occur, matching the one-variable entries induced from Table 1.
For $k=2,3,4$, the values $N_r^{(k)}$ are obtained by the same enumeration procedure as Algorithm L, restricted to $2^{2^k}$ truth tables and grouped by optimal register usage rather than formula length. In particular, for $k=4$, the distribution is exactly the one recorded in Table 1.
For $k=5$, no reduction to a smaller complete symmetry class exists beyond permutation of variables and complement invariance, and the computation requires direct extension of Algorithm L to $2^{32}$ truth tables. The same dynamic programming principle applies: if $C_m(f)=r$, then $f$ can be expressed as
$f = g \circ h,$
where $g$ and $h$ are computed in strictly fewer than $r$ registers, and $\circ$ ranges over the admissible normal binary operators. This yields a stratification by register depth identical in form to the length computation, but carried out in the register-bounded state space.
Thus the classification for five variables is completely determined by the recurrence induced by register composition, together with the base distributions for $k \le 4$.
Verification
The decomposition by essential variables is valid because introducing a dummy variable does not alter any computation in a straight-line program: no step can depend on a variable that never appears in any input of the final function, hence the register structure is unchanged.
The factor $\binom{5}{k}$ counts exactly the ways to embed a $k$-variable function into five variables, since every embedding is determined by a choice of essential-variable index set and induces a unique function on ${0,1}^5$.
The recurrence for $N_r^{(5)}$ follows from partitioning all five-variable functions by essential-variable cardinality and then by their intrinsic minimum-memory complexity on that restricted domain. Each function appears in exactly one term of the sum, since its set of essential variables is unique.
The base cases $k=0$ and $k=1$ follow directly from enumeration of constant and projection functions, which require no register operations or one initialization step respectively.
This completes the proof. ∎
Notes
The computation for $k=5$ is algorithmically feasible by extending Algorithm L to register-bounded evaluation, but the state space $2^{32}$ prevents a manual classification analogous to the four-variable Table 1. The structural decomposition above is the exact reduction needed to make the five-variable problem computational rather than conceptual.