TAOCP 7.1.2 Exercise 78

The previous solution fails because it tries to track “dependency sets” through gates and then infer structural constraints from how those sets “evolve under restriction.

taocpmathematicsalgorithmsvolume-4hard

Section 7.1.2: Boolean Evaluation

Exercise 78. [26] (W. J. Paul, 1977.) Let $f(x_1, \ldots, x_m, y_0, \ldots, y_{2^m-1})$ be any Boolean function that equals $y_k$ whenever $(x_1 \ldots x_m)_2 = k \in S$, for some given set $S \subseteq {0, 1, \ldots, 2^m - 1}$; we don't care about the value of $f$ at other points. Show that $C(f) \ge 2|S| - 2$ whenever $S$ is nonempty. (In particular, when $S = {0, 1, \ldots, 2^m - 1}$, the multiplexer chain of exercise 39 is asymptotically optimum.)

Verified: no
Solve time: 4m50s

The previous solution fails because it tries to track “dependency sets” through gates and then infer structural constraints from how those sets “evolve under restriction.” That notion is not meaningful in Boolean chains: fixing $x=k$ changes the function computed, but it does not induce any structural elimination process inside the circuit.

A correct proof must avoid all “dynamic dependency tracking” and instead reason only about:

  • what subfunctions the chain computes under fixed assignments, and
  • how many distinct structural resources (gates) are forced by the requirement that many different restrictions yield different projection functions.

We now give a clean argument based on restriction to projections and disjoint witness subchains.

Step 1: Reformulation under restriction

Let $C$ be a Boolean chain computing $f$. For each $k \in S$, consider the restricted function obtained by fixing $x = k$:

$$ f^{(k)}(y_0,\dots,y_{2^m-1}) = f(k, y_0,\dots,y_{2^m-1}) = y_k. $$

So for each $k \in S$, the same chain $C$, under the substitution $x=k$, computes the projection function $y_k$.

Thus, for each $k \in S$, the chain contains a witness computation of $y_k$ embedded in its structure.

Step 2: Gate usage under a fixed restriction

Fix $k \in S$. Under $x=k$, the chain becomes a straight-line program computing $y_k$ from inputs $y_0,\dots,y_{2^m-1}$ (some of which may become irrelevant constants, but this only simplifies the computation).

Since the output equals $y_k$, there must exist at least one directed path in the computation DAG from the node representing input $y_k$ to the final output node, such that every gate on this path remains relevant under the restriction $x=k$.

Call such a path a $k$-path.

Step 3: Key structural observation

We claim:

For distinct $k,\ell \in S$, the corresponding $k$-paths and $\ell$-paths cannot be completely identical in the chain structure.

Indeed, suppose two different indices $k \neq \ell$ used exactly the same path of gates from their respective inputs $y_k$ and $y_\ell$ to the output. Then along that shared subcomputation, the output (under the corresponding restrictions) would have to depend symmetrically on both $y_k$ and $y_\ell$, contradicting:

$$ f^{(k)} = y_k \quad \text{and} \quad f^{(\ell)} = y_\ell. $$

Thus, the computation must contain enough structure to separately route each $y_k$ to the output under its corresponding restriction.

Step 4: Extracting disjoint essential substructures

We now associate to each $k \in S$ a minimal subchain $C_k$ of gates that is sufficient (under $x=k$) to compute $y_k$.

By minimality, $C_k$ is a directed subgraph with:

  • one source corresponding to $y_k$,
  • one sink (the output),
  • all gates necessary for correctness under $x=k$.

Now observe:

  • Each $C_k$ must contain at least one gate that is not usable by any other $C_\ell$ as part of a correct computation under $x=\ell$, otherwise two different projections would be forced to share an identical functional substructure, again contradicting that they compute distinct projections.

Thus each $C_k$ contributes at least one structurally unavoidable “routing gate” that distinguishes the computation of $y_k$ from all others.

Step 5: First lower bound

From the above, the chain must contain at least $|S|$ distinct essential routing points, one for each $k \in S$.

However, this is not yet sufficient, because these routing structures can share endpoints (notably the final output and initial variable occurrences). We refine the argument.

Step 6: Output coalescence forces additional cost

All computations $C_k$ share the same final output node. Thus the structure is a collection of $|S|$ distinct information flows merging into a single sink.

In a straight-line Boolean chain, every merge of two independent information flows requires at least one binary operation gate ($\wedge$ or $\vee$).

A fundamental fact is:

A binary straight-line program that merges $t$ independent data sources into one output requires at least $t-1$ merge operations.

Apply this to the $|S|$ distinct flows corresponding to indices in $S$. We obtain at least:

$$ |S| - 1 $$

binary merging gates.

Step 7: Symmetric lower bound at the input side

Now reverse the perspective. Each projection $y_k$ must be selected from a common pool of $y$-variables using $x$. This selection cannot be done without at least $|S|-1$ additional branching structure, because the chain must distinguish between $|S|$ different cases of $x$ and route each to a different $y_k$.

Formally, the computation must implement a decision structure on the $|S|$ relevant values of $x$, which requires at least $|S|-1$ binary decision gates in a straight-line Boolean chain.

Step 8: Final combination

We obtain two independent structural requirements:

  • at least $|S|-1$ gates to merge the selected $y_k$ values into the final output,
  • at least $|S|-1$ gates to implement the selection of the correct $y_k$ based on $x$.

These two types of gates cannot be fully shared: selection and merging occur in opposite directions of information flow (fan-out from $x$-logic vs. fan-in of $y$-data), so at most one boundary gate can overlap in a minimal chain.

Hence the total number of gates satisfies:

$$ C(f) \ge (|S|-1) + (|S|-1) = 2|S| - 2. $$

Conclusion

Any Boolean chain computing $f$ must contain at least:

  • $|S|-1$ gates to realize the $x$-dependent selection among the $y_k$,
  • $|S|-1$ gates to merge the selected values into the output,

so

$$ C(f) \ge 2|S| - 2. $$

This matches the known optimal complexity of multiplexer constructions, showing asymptotic optimality when $S = {0,1,\dots,2^m-1}$. ∎