TAOCP 7.1.2 Exercise 38

Let the inputs be $x_1,\dots,x_n \in \{0,1\}$, and let t=\sum_{j=1}^n x_j be the number of ones.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.2: Boolean Evaluation

Exercise 38. [25] In Section 5.3.4 we studied sorting networks, by which $S(n)$ comparator modules are able to sort $n$ numbers $(x_1, x_2, \ldots, x_n)$ into ascending order. If the inputs $x_j$ are 0s and 1s, each comparator module is equivalent to two gates $(x \wedge y, x \vee y)$; so a sorting network corresponds to a certain kind of Boolean chain, which evaluates $n$ particular functions of $(x_1, x_2, \ldots, x_n)$.

a) What are the $n$ functions $f_1 f_2 \ldots f_n$ that a sorting network computes? b) Show that those functions ${f_1, f_2, \ldots, f_n}$ can be computed in $O(n)$ steps with a Boolean chain of depth $O(\log n)$. (Hence sorting networks aren't asymptotically optimal, Boolean-wise.)

Verified: no
Solve time: 6m52s

Corrected solution to Exercise 7.1.2.38

(a) Functions computed by a sorting network on ${0,1}^n$

Let the inputs be $x_1,\dots,x_n \in {0,1}$, and let

$$ t=\sum_{j=1}^n x_j $$

be the number of ones.

A sorting network outputs the sorted sequence, hence

$$ (\underbrace{0,\dots,0}{n-t},\underbrace{1,\dots,1}{t}). $$

Therefore the $k$-th output is 1 exactly when at least $n-k+1$ ones are present:

$$ f_k(x_1,\dots,x_n)=1 \iff t \ge n-k+1. $$

Equivalently, the functions are the threshold functions

$$ f_k = [t \ge n-k+1], \qquad k=1,\dots,n. $$

So the network computes all threshold functions for thresholds $1,2,\dots,n$, arranged in reverse order.

(b) Boolean chain of size $O(n)$ and depth $O(\log n)$

We construct a Boolean circuit (Boolean chain) computing all functions

$$ f_k = [t \ge k], \qquad k=1,\dots,n, $$

where $t=\sum_{j=1}^n x_j$.

The construction has two parts.

Step 1: compute the binary representation of $t$

We compute $t$ using a balanced binary adder tree.

At each internal node, we combine two partial sums represented in binary using a carry-save style addition followed by a carry-propagate reduction.

Facts:

  • Each addition of two $O(\log n)$-bit numbers is implemented with $O(\log n)$ gates.
  • The tree has $O(n)$ inputs and $O(n)$ total wires per level.
  • The depth is $O(\log n)$.

Hence we obtain the binary expansion

$$ t = \sum_{i=0}^{\lfloor \log n \rfloor} 2^i t_i $$

in total:

  • size $O(n)$,
  • depth $O(\log n)$.

Step 2: convert the binary number $t$ into all thresholds

We now construct all bits

$$ f_k = [t \ge k], \qquad k=1,\dots,n. $$

Key reformulation

Define the unary vector of $t$:

$$ u_k = [t \ge k]. $$

This is exactly the prefix indicator of the integer $t$. Our task is to compute the unary encoding of a binary number.

Step 2A: segment tree over thresholds

We build a complete binary tree over the index set ${1,\dots,n}$.

Each node $v$ corresponds to an interval $I_v = [a,b]$ and stores a single Boolean value:

$$ U_v = [t \ge a]. $$

We compute these values top-down.

  • Root corresponds to $[1,n]$.
  • If a node $v$ corresponds to $[a,b]$, split into:

$$ [a,m], \quad [m+1,b]. $$

We compute a single comparison:

$$ C_v = [t \ge m+1]. $$

Then:

  • left child receives $U_{\text{left}} = U_v$,
  • right child receives $U_{\text{right}} = U_v \wedge C_v$.

Thus each node performs only constant Boolean operations once its comparison bit $C_v$ is known.

Step 2B: computing comparisons $C_v = [t \ge k]$

Each comparison is between:

  • the binary number $t$,
  • a fixed constant $k$.

We compute all such comparisons using a shared bitwise comparison circuit.

Write:

$$ t = (t_m,\dots,t_0), \quad k = (k_m,\dots,k_0). $$

We compute

$$ [t \ge k] $$

by the standard lexicographic comparison:

Define signals $E_i, G_i$:

  • $E_i$: all higher bits equal,
  • $G_i$: first differing bit is $t_i=1, k_i=0$.

Recurrence:

$$ E_{i-1} = E_i \wedge (t_i \leftrightarrow k_i), $$

$$ G_{i-1} = G_i \vee (E_i \wedge t_i \wedge \neg k_i), $$

with initialization $E_m=1, G_m=0$.

Output is $G_0$.

Crucial sharing argument

We compute comparisons for all segment tree nodes simultaneously.

At bit level $i$:

  • each node contributes only constant many AND/OR/NOT gates,
  • each gate depends only on $t_i$ and a constant $k_i$,
  • each $t_i$ feeds into $O(n/2^i)$ nodes at level $i$,
  • but each appearance is realized by fan-out wiring of a single computed signal $t_i$, not duplication of gates.

Hence:

  • each bit $t_i$ participates in $O(n)$ wires total across all levels,
  • but only $O(1)$ gates per node per level are created,
  • and the total number of nodes across all levels is $O(n)$.

Therefore total comparison-circuit size is:

$$ O(n). $$

Depth is:

$$ O(\log n) $$

(from bitwise comparison + tree depth).

Step 2C: final assembly of unary outputs

Once all node comparisons $C_v$ are computed:

  • each leaf $k$ receives value $u_k = [t \ge k]$,
  • propagation uses only AND gates along a root-to-leaf path,
  • each level contributes $O(n)$ gates total.

Thus unary reconstruction adds:

  • size $O(n)$,
  • depth $O(\log n)$.

Final complexity

Size

  • binary adder tree: $O(n)$,
  • comparison network (shared across segment tree): $O(n)$,
  • unary propagation: $O(n)$.

Total:

$$ O(n). $$

Depth

  • addition: $O(\log n)$,
  • comparisons: $O(\log n)$,
  • propagation: $O(\log n)$.

Total:

$$ O(\log n). $$

Conclusion

We have constructed a Boolean chain that:

  1. computes $t=\sum x_j$ in binary in $O(n)$ size and $O(\log n)$ depth,
  2. computes all threshold comparisons $[t \ge k]$ using a shared comparison and segment tree structure in $O(n)$ size,
  3. outputs all $n$ threshold functions.

Hence the family ${f_1,\dots,f_n}$ is computable by a Boolean chain of

$$ \boxed{\text{size } O(n), \quad \text{depth } O(\log n)}. $$

This shows sorting networks are not asymptotically optimal in Boolean circuit complexity terms. ∎