TAOCP 7.1.2 Exercise 26

The statement is **false**.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.2: Boolean Evaluation

Exercise 26. [25] [25] True or false: If $f(x_3, \ldots, x_n) = (x_0 \wedge g(x_1, \ldots, x_n)) \oplus h(x_1, \ldots, x_n)$, where $g$ and $h$ are nontrivial Boolean functions whose joint cost is $C(gh)$, then $C(f) = 2 + C(gh)$.

Verified: no
Solve time: 4m33s

The statement is false.

Only the upper bound

$$ C(f)\le C(gh)+2 $$

is valid in general. The claimed equality fails because there is no reason that an optimal computation of $f$ must internally realize a joint optimal computation of $g$ and $h$.

1. Why the upper bound is correct

Start with an optimal straight-line program that jointly computes $g(x_1,\dots,x_n)$ and $h(x_1,\dots,x_n)$ using $C(gh)$ operations.

From these outputs, compute:

$$ t := x_0 \wedge g $$

$$ f := t \oplus h $$

This adds exactly two operations, so

$$ C(f)\le C(gh)+2. $$

This part is valid.

2. Why the lower bound argument fails

The proposed proof attempts to argue:

  • Setting $x_0=0$ forces $f=h$
  • Setting $x_0=1$ forces $f=g\oplus h$
  • Therefore any computation of $f$ must “contain” computations of $g$ and $h$
  • Hence cost at least $C(gh)$

This is incorrect in the straight-line program model.

A restriction such as $f(0,x)=h(x)$ does not imply that a program computing $f$ computes $h$ as an intermediate value. The circuit may compute $f$ through shared or entangled expressions that never isolate $g$ or $h$ as standalone subresults.

So there is no valid reason that:

$$ C(f)\ge C(gh) $$

must hold.

3. Structural obstruction to equality

The key issue is that $C(gh)$ measures the cost of producing both outputs simultaneously, but computing $f$ only requires a single output.

There is no monotonicity relation forcing:

$$ C(f) \ge C(gh) $$

because a circuit computing a single Boolean function can reuse structure in ways that are not available when forcing two outputs.

In particular, $f$ can be rewritten as:

$$ f = (x_0 \wedge g)\oplus h $$

or equivalently:

$$ f = (x_0 \wedge (g\oplus h)) \oplus (\neg x_0 \wedge h). $$

This shows that $f$ can be computed from combinations of $h$ and $g\oplus h$, not necessarily from $g$ and $h$ separately.

The joint complexity $C(gh)$ may be strictly larger than the cost of computing a more efficient derived pair such as $(h, g\oplus h)$, or even larger than what is needed to assemble $f$.

Nothing in the model guarantees:

$$ C(gh) \le C(f)-2. $$

4. Where equality breaks

The equality claim requires:

$$ C(f)\ge C(gh)+2 $$

but this implicitly assumes:

  • Any computation of $f$ must compute both $g$ and $h$ as intermediates
  • Any such computation must be at least as expensive as the optimal joint computation of $(g,h)$

Both assumptions are false. A circuit for $f$ is not required to simulate a joint transducer for $(g,h)$, and may avoid computing either function explicitly.

5. Conclusion

We always have:

$$ C(f)\le C(gh)+2, $$

but the reverse inequality fails in general because computing a single Boolean function does not force the circuit to realize the joint optimal computation of two output functions.

Therefore:

$$ \boxed{C(f)\ne C(gh)+2 \text{ in general, and the statement is false.}} $$