TAOCP 7.1.2 Exercise 35

Section 7.1.2: Boolean Evaluation

Exercise 35. [23] If $n > 1$, show that the conjunctions $\bar{x}1 \wedge \cdots \wedge x{k-1} \wedge x_{k+1} \wedge \cdots \wedge x_n$ for $1 \le k \le n$ can all be computed from $(x_1, \ldots, x_n)$ with total cost $\le 3n - 6$.

Verified: no
Solve time: 11m20s