TAOCP 7.1.2 Exercise 25
Let $m = 2^{2^n}$, and let $f_0,\dots,f_{m-1}$ be the enumeration of all Boolean functions of $n$ variables, where $f_k(x_1,\dots,x_n)$ is defined by the binary expansion of $k$.
Section 7.1.2: Boolean Evaluation
Exercise 25. ▶ [17] [17] Suppose we want a Boolean chain that includes all functions of $n$ variables: Let $f_k(x_1, \ldots, x_n)$ be the function whose truth table is the binary representation of $k$, for $0 \le k < m = 2^{2^n}$. What is $C(f_0 f_1 \ldots f_{m-1})$?
Verified: yes
Solve time: 2m18s
Let $m = 2^{2^n}$, and let $f_0,\dots,f_{m-1}$ be the enumeration of all Boolean functions of $n$ variables, where $f_k(x_1,\dots,x_n)$ is defined by the binary expansion of $k$.
We consider the function
$$ g(x_1,\dots,x_n) = f_0(x_1,\dots,x_n), f_1(x_1,\dots,x_n)\cdots f_{m-1}(x_1,\dots,x_n), $$
where juxtaposition denotes Boolean conjunction.
Step 1: Identify the value of the product function
Fix an input $x \in {0,1}^n$. As $k$ ranges over $0 \le k < m$, the functions $f_k$ range over all Boolean functions on $n$ variables.
For a fixed $x$, half of all Boolean functions satisfy $f(x)=1$, and half satisfy $f(x)=0$. Hence among the $m = 2^{2^n}$ functions, there exist many $k$ such that $f_k(x)=0$.
Therefore,
$$ g(x) = \prod_{k=0}^{m-1} f_k(x) = 0, $$
because at least one factor in the product is $0$.
Since this holds for every input $x$, the function $g$ is identically zero:
$$ g \equiv 0. $$
Step 2: Compute $C(g)$
The quantity $C(\cdot)$ denotes the complexity of a Boolean chain computing the function. The constant zero function requires no logical operations to represent if constants are allowed as primitives in the chain formalism; equivalently, it can be represented directly as the constant $0$.
Thus the minimal complexity is
$$ C(0) = 0. $$
Conclusion
$$ C(f_0 f_1 \cdots f_{m-1}) = 0. $$