Exercise 11. ▶ [22] Modify Algorithm L so that, instead of lengths $L(f)$, it computes upper bounds $U(f)$ and footprints $\phi(f)$ as described in the text.

Verified: no
Solve time: 8m11s

The previous solution fails because it silently turned $U(f)$ into an exact-length function by assuming global optimality of decompositions. The corrected construction must treat $U(f)$ purely as a maintained upper bound produced by the algorithm, without any appeal to global minimality or completeness of enumeration.

The key change is conceptual:

$U(f)$ is not “the best possible length of a chain for $f$” in the global sense.
It is the value produced by Algorithm L under modified update rules, and must be proved to always satisfy $U(f) \ge L^\ast(f)$, where $L^\ast(f)$ is the true minimal chain length.

The footprint $\phi(f)$ is then maintained relative to this evolving bound, not relative to an optimality notion.

Corrected Solution

We modify Algorithm L so that each Boolean function $f$ is assigned:

an upper bound $U(f)$ on the length of a normal Boolean chain computing $f$,
a footprint $\phi(f)$, a bit vector indexed by admissible first-step choices in a normal chain.

The algorithm constructs values inductively in the same enumeration framework as Algorithm L, but with a different interpretation of the length register.

1. Meaning of $U(f)$

Let $L^\ast(f)$ denote the true minimal length of a normal Boolean chain computing $f$.

We maintain the invariant:

$$ U(f) \ge L^\ast(f) $$

Thus $U(f)$ is only required to be a correct upper bound, not the exact value.

No assumption of optimality of discovered decompositions is made.

2. Initialization

For constants and variables:

$$ U(0)=U(1)=0,\qquad U(x_k)=0. $$

These are valid because constant and variable functions are computable with no binary operation steps in a normal chain.

Footprints are initialized as empty:

$$ \phi(0)=\phi(1)=\phi(x_k)=\mathbf{0}. $$

3. Candidate construction step

Suppose a new function is formed from previously constructed functions via a normal binary operation:

$$ f = g \circ h. $$

If $g$ and $h$ have already assigned upper bounds $U(g)$, $U(h)$, then we can construct a valid chain for $f$ by concatenation:

a chain computing $g$,
a chain computing $h$,
one final operation.

Hence this yields a valid chain length:

$$ r = U(g) + U(h) + 1. $$

Crucially, this is not assumed optimal, only valid.

Therefore $r$ is a legitimate upper bound candidate for $f$.

4. Update rule for $U(f)$

Algorithm L maintains the best known upper bound discovered so far:

$$ U(f) \leftarrow \min\big(U(f),, r\big), $$

with initialization $U(f)=\infty$ if undefined.

Correctness of the update

We prove the invariant $U(f)\ge L^\ast(f)$:

Initially true for base functions.
If $U(g)\ge L^\ast(g)$ and $U(h)\ge L^\ast(h)$, then

$$ r = U(g)+U(h)+1 \ge L^\ast(g)+L^\ast(h)+1 \ge L^\ast(f), $$

since concatenation produces a valid chain for $f$.

Taking a minimum of valid upper bounds preserves being an upper bound.

Thus every stored value remains a correct upper bound.

5. Footprint definition

The footprint records which first-step choices occur in constructions that achieve the current recorded bound $U(f)$.

We treat footprints as tied to the current best known bound, not to any global optimality notion.

Update rule

For a decomposition $f=g\circ h$ with candidate value $r$:

If $r > U(f)$: ignore it (it is not competitive).
If $r < U(f)$: we have found a strictly better upper bound, so reset:

$$ U(f)\leftarrow r,\qquad \phi(f)\leftarrow \phi(g)\lor \phi(h). $$

If $r = U(f)$: this is an alternative construction achieving the same bound, so:

$$ \phi(f)\leftarrow \phi(f)\lor \phi(g)\lor \phi(h). $$

Interpretation

$\phi(f)$ always represents:

the union of first-step patterns of all constructions currently achieving the best known upper bound for $f$.

No claim is made that this bound is globally optimal.

6. First-step justification (correct form)

Let $C$ be any chain produced by a decomposition $f=g\circ h$. The first operation of $C$ lies entirely within the subchain computing either $g$ or $h$, since the final operation is strictly last.

Therefore the first-step set of the full chain is contained in:

$$ \phi(g)\cup \phi(h), $$

and no new first-step arises from the final composition step.

This is structural and independent of any optimality assumption.

7. Key invariant for footprints

We maintain:

$$ \phi(f)=\bigcup \left{\phi(g)\cup \phi(h);:; f=g\circ h,; U(g)+U(h)+1 = U(f)\right}, $$

with updates performed incrementally by Algorithm L.

Thus footprints depend only on currently minimal discovered upper-bound constructions, not on globally optimal chains.

8. Correctness summary

Upper bound correctness

By induction over construction steps:

base functions satisfy $U(f)=0$,
every derived value $r$ corresponds to an explicit valid chain,
taking minima preserves validity.

Hence:

$$ U(f)\ge L^\ast(f)\quad \text{for all } f. $$

Footprint correctness

For each function $f$, $\phi(f)$ records exactly the union of first-step patterns of all constructions that currently achieve the best known upper bound $U(f)$. This follows directly from the update rules and structural decomposition of normal chains.

No assumption of global optimality or completeness of enumeration is required.

Final statement

The modified Algorithm L is obtained by:

interpreting $U(f)$ as a maintained upper bound, not an exact or optimal length,
updating $U(f)$ via minima of valid chain-length constructions,
propagating footprints only through decompositions achieving the current best bound,
resetting footprints whenever a strictly better upper bound is found.

This yields a consistent simultaneous computation of upper bounds $U(f)$ and footprints $\phi(f)$ within the structure of Algorithm L. ∎

TAOCP 7.1.2 Exercise 11