TAOCP 5.3.4 Exercise 33

Assume, for a contradiction, that there exists a comparator network with inputs \(x_1,\dots ,x_n\) and an output line that computes \[ f(x_1,x_2,x_3,x_4)=(x_1\land x_2)\lor(x_2\land x_3)\lor(x_3\land...

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.4: Networks for Sorting

Exercise 33. ▶ [M22] Not all $\delta_n$ of the functions of $\langle x_1, \ldots, x_n \rangle$ in exercise 31 can appear in comparator networks. In fact, prove that the function $(x_1 \wedge x_2) \vee (x_2 \wedge x_3) \vee (x_3 \wedge x_4)$ cannot appear as an output of any comparator network on $\langle x_1, \ldots, x_n \rangle$.

Verified: no
Solve time: 1h20m

Solution

Assume, for a contradiction, that there exists a comparator network with inputs (x_1,\dots ,x_n) and an output line that computes

[ f(x_1,x_2,x_3,x_4)=(x_1\land x_2)\lor(x_2\land x_3)\lor(x_3\land x_4). ]

Set all extra inputs (x_5,\dots ,x_n) to (0); they then act as constant zeros.
Thus we may suppose (n=4) and the network has four lines.

In a comparator network the multiset of values is preserved, so the value on any output line is always the value of some input line. For each assignment we let (s(x_1,x_2,x_3,x_4)) be the index of the input line whose value appears on the output.

Consider the following six assignments (each with exactly two (1)’s):

[ \begin{aligned} A&=(1,1,0,0), & f(A)&=1,\ B&=(0,1,1,0), & f(B)&=1,\ C&=(0,0,1,1), & f(C)&=1,\ D&=(1,0,1,0), & f(D)&=0,\ E&=(1,0,0,1), & f(E)&=0,\ F&=(0,1,0,1), & f(F)&=0. \end{aligned} ]

Because the output equals the value of some input line, we obtain local constraints on (s):

  • From (A) and (D): the only line that is (1) in (A) and (0) in (D) is line (2). Hence (s(A)=s(D)=2).
  • From (B) and (E): the only line that is (1) in (B) and (0) in (E) is line (3). Hence (s(B)=s(E)=3).
  • From (C) and (F): the only line that is (1) in (C) and (0) in (F) is line (3). Hence (s(C)=s(F)=3).

In particular, (s(A)=2) and (s(B)=3).
Thus the network must be able to route the value of line (2) to the output when the data are given by (A) and the value of line (3) when the data are given by (B).
The only way to change which input line supplies the output is to exchange values between lines by means of comparators. Therefore the network must at some stage compare the values on the lines that originally carry (x_2) and (x_3).

Now examine assignments (A) and (D):

[ A:;(x_2,x_3)=(1,0),\qquad D:;(x_2,x_3)=(0,1). ]

Suppose a comparator is applied to the lines that originally hold (x_2) and (x_3). After the comparator the two lines carry (\min(x_2,x_3)) and (\max(x_2,x_3)). If the comparator is oriented in a fixed way (the standard convention is that the smaller value goes to the line with the smaller index), then after the comparator the values on the two lines become

[ \text{line }2\gets\max(x_2,x_3),\qquad \text{line }3\gets\min(x_2,x_3). ]

In both (A) and (D) we obtain the same pair: line (2) carries (1), line (3) carries (0). Consequently the entire subsequent state of the network is identical for (A) and (D), and the output must be the same. But (f(A)=1) and (f(D)=0) - a contradiction.

If the comparator is oriented in the opposite way, the same contradiction arises because the roles of lines (2) and (3) are simply exchanged; the state after the comparator is again identical in (A) and (D).

Hence no comparator network can produce (f) as an output. This completes the proof.

∎