TAOCP 5.3.4 Exercise 52

We consider the family of comparator networks shown in Fig.

taocpmathematicsalgorithmsvolume-3hard

Section 5.3.4: Networks for Sorting

Exercise 52. ▶ [32] (M. O. Rabin, 1980.) Prove that it is intrinsically difficult to decide in general whether a sequence of comparators defines a sorting network, by considering networks of the form sketched in Fig. 60. It is convenient to number the inputs $x_0$ to $x_N$, where $N = 2mn + m + 2n$; the positive integers $m$ and $n$ are parameters. The first comparators are $[j:j+2nk]$ for $1 \le j \le 2n$ and $1 \le k \le m$. Then we have $[2j-1:2j][0:2j]$ for $1 \le j \le n$, in parallel with a special subnetwork that uses only indices $> 2n$. Next we compare $[0:2mn+2n+j]$ for $1 \le j \le m$. And finally there is a complete sorting network for $\langle x_1, \dots, x_N \rangle$, followed by $[0:1][1:2] \dots [N-t-1:N-t]$, where $t = mn+n+1$.

a) Describe all inputs $\langle x_0, x_1, \dots, x_N \rangle$ that are not sorted by such a network, in terms of the behavior of the special subnetwork.

b) Given a set of clauses such as $(y_1 \vee y_2 \vee \bar{y}_3) \wedge (\bar{y}_2 \vee y_3 \vee \bar{y}_4) \wedge \dots$, explain how to construct a special subnetwork such that Fig. 60 sorts all inputs if and only if the clauses are unsatisfiable. [Hence the task of deciding whether a comparator sequence forms a sorting network is co-NP-complete, in the sense of Section 7.9.]

Verified: no
Solve time: 15m23s

Setup

We consider the family of comparator networks shown in Fig. 60, parameterized by positive integers (m) and (n).
The inputs are (x_0,x_1,\dots,x_N) with (N = 2mn + m + 2n).
The network consists of four stages:

  1. First stage: comparators ([j : j+2nk]) for (1\le j\le 2n) and (1\le k\le m).
  2. Second stage: comparators ([2j-1:2j][0:2j]) for (1\le j\le n), executed in parallel with a special subnetwork that uses only lines with indices (>2n).
  3. Third stage: comparators ([0 : 2mn+2n+j]) for (1\le j\le m).
  4. Fourth stage: a complete sorting network on lines (1,\dots,N), followed by adjacent comparators
    ([0:1][1:2]\dots[N-t-1:N-t]) where (t = mn+n+1).

The special subnetwork is a fixed comparator network whose inputs are the values on lines (2n+1,\dots,N) after stage 1 and whose outputs are on the same lines.
By the zero-one principle we may restrict attention to inputs (x_i\in{0,1}).

Solution

Part (a)

Let an input (X = (x_0,x_1,\dots,x_N)) be given.
For (j=1,\dots,2n) define

[ M_j = \min\bigl(x_j,; x_{j+2n},; x_{j+4n},; \dots,; x_{j+2nm}\bigr). ]

After stage 1 the lines (1,\dots,2n) contain exactly (M_1,\dots,M_{2n}).
Let (V) be the vector of values on lines (2n+1,\dots,N) after stage 1; this is the input to the special subnetwork.
Let (W = S(V)) be the output of the special subnetwork, and denote the last (m) components of (W) by

[ y_k = W_{2mn+2n+k}\qquad (k=1,\dots,m). ]

Stage 2 transforms lines (0,\dots,2n). Because the comparators ([2j-1:2j]) and ([0:2j]) are applied sequentially for (j=1,\dots,n), the value on line 0 after stage 2 is

[ L_0 = \min\bigl(x_0,; \max(M_1,M_2),; \max(M_3,M_4),; \dots,; \max(M_{2n-1},M_{2n})\bigr). ]

Stage 3 compares line 0 with the last (m) lines of the special subnetwork. The value on line 0 after stage 3 is therefore

[ v = \min\bigl(L_0,; y_1,\dots,y_m\bigr). ]

Finally, stage 4 sorts lines (1,\dots,N) completely and then merges line 0 into the first (N-t = mn+m+n-1) positions.
For 0‑1 sequences the whole network produces a sorted output iff it is not the case that (v=1) and the number of zeros among lines (1,\dots,N) after stage 3 is at least (mn+m+n).

Let (Z) be the number of zeros on lines (1,\dots,N) after stage 3.
Since the total multiset of lines (0,\dots,N) is invariant, and line 0 changes from (x_0) to (v), we have

[ Z = #{i\in{1,\dots,N}\mid x_i=0} + (x_0==0) - (v==0). ]

If (v=1) then (x_0=1) (otherwise (L_0=0)) and (Z = #{i\ge 1\mid x_i=0}).
Thus the network fails to sort (X) exactly when the following four conditions hold simultaneously:

  1. (x_0 = 1).
  2. (\max(M_{2j-1},M_{2j}) = 1) for all (j=1,\dots,n).
  3. The special subnetwork outputs (y_1=y_2=\dots=y_m=1).
  4. (\displaystyle\sum_{i=1}^N (1-x_i) ;\ge; mn+m+n).

This characterises all unsorted inputs purely in terms of the behaviour of the special subnetwork (condition 3) and simple properties of the fixed part of the network.

Part (b)

Let a CNF formula be given with variables (y_1,\dots,y_n) and clauses (C_1,\dots,C_m).
We build the special subnetwork (S) as follows.

Associate chains with literals:
For each variable (y_i) ((1\le i\le n)) let chain (2i-1) represent the literal (y_i) and chain (2i) represent the literal (\bar y_i).
Chain (j) consists of the lines (j+2n,; j+4n,; \dots,; j+2nm) (its (k)-th element is line (j+2nk)).
The extra block is the set of lines (2n(m+1)+1,\dots,N); its (k)-th line is exactly the (k)-th line among the last (m) lines, i.e. line (2mn+2n+k).

Construct (S):
For each clause (C_k) ((1\le k\le m)) and for each literal occurring in (C_k), add the comparator

[ \bigl[,2n(m+1)+k ;:; j+2nk,\bigr], ]

where (j = 2i-1) if the literal is (y_i) and (j = 2i) if the literal is (\bar y_i).
No other comparators are placed in the special subnetwork.
(The order of these comparators is immaterial because they involve disjoint pairs of lines for different (k).)

Verification of the reduction.

((\Rightarrow)) Suppose the overall network fails to sort some input (X).
By part (a) conditions 1-4 hold.
Condition 4 forces the number of zeros among (x_1,\dots,x_N) to be at least (mn+m+n).
The total number of lines available is (N = 2mn+m+2n).
Condition 2 implies that for each (i=1,\dots,n) at least one of the two chains (2i-1,2i) has all its (m+1) entries (including the head (x_j)) equal to 1.
Hence that chain contributes no zeros. The other chain can contribute at most (m+1) zeros.
Summing over all (n) variables and adding the extra block of size (m) gives at most (n(m+1)+m = mn+m+n) zeros.
Therefore the zero count is exactly (mn+m+n) and the extremal configuration is forced:

  • For each (i), one chain is entirely (1)s (its (x_j=1) and all its (m) elements are 1) and the other chain is entirely (0)s (its (x_j=0) and all its (m) elements are 0).
  • The extra block is entirely (0)s.

Define a truth assignment by setting (y_i = \text{true}) iff chain (2i-1) is the all‑1 chain.
Because the special subnetwork outputs (1) on the last (m) lines (condition 3), and each extra line (k) has been compared with exactly the chain lines corresponding to the literals in clause (C_k), the value on extra line (k) becomes the maximum of the initial (0) and those literals’ lines.
In the extremal configuration a literal’s line is (1) exactly when that literal is true.
Thus extra line (k) ends as (1) iff clause (C_k) contains at least one true literal.
Since all extra lines are (1), every clause is satisfied. Hence the CNF is satisfiable.

((\Leftarrow)) Suppose the CNF is satisfiable. Choose a satisfying assignment.
Construct an input (X) as follows:

  • (x_0 = 1).
  • For each (i=1,\dots,n): if (y_i=\text{true}) set chain (2i-1) entirely to (1) (including (x_{2i-1}=1)) and chain (2i) entirely to (0) (including (x_{2i}=0)); if (y_i=\text{false}) do the opposite.
  • Set the extra block entirely to (0).

Then condition 1 holds.
For each (i), (\max(M_{2i-1},M_{2i}) = \max(1,0)=1), so condition 2 holds.
The total zeros among (x_1,\dots,x_N) are exactly (n(m+1)+m = mn+m+n), satisfying condition 4.
Because the assignment satisfies every clause, the special subnetwork will produce (1) on each extra line, so condition 3 holds.
By part (a) this input makes the network fail to sort.

Therefore the network sorts all inputs if and only if the given CNF is unsatisfiable.
∎

Verification

The most delicate step is the zero‑count argument in part (b). We verify it independently:

Total lines among the lines (1,\dots,N):
There are (2n) chains, each of length (m) plus its head line (x_j) ((2n) lines), and an extra block of (m) lines.
Total lines = (2n(m+1)+m = 2mn+m+2n = N).
If condition 2 holds, each pair of chains ((2i-1,2i)) has at least one chain with (M_j=1), meaning that chain’s (m+1) entries are all 1.
Hence that pair contributes at most (m+1) zeros (all from the other chain).
The extra block contributes at most (m) zeros.
Maximum total zeros = (n(m+1)+m = mn+m+n).
Condition 4 requires at least this many zeros, so equality is forced and the extremal configuration described is the only possibility.

Special subnetwork correctness:
In the extremal configuration the input to (S) consists of (n) chains of (1)s, (n) chains of (0)s, and an extra block of (0)s.
The comparators added for clause (k) are between extra line (k) (initially 0) and the (k)-th line of each chain whose literal appears in (C_k).
Because the chains are uniform, the (k)-th line of a chain is (1) iff the corresponding literal is true.
A sequence of max‑operations (comparators) between the extra line and those literal lines leaves the extra line equal to the logical OR of the literals in (C_k).
Since the assignment satisfies the formula, every extra line becomes 1.
Conversely, if some clause were unsatisfied, its extra line would stay 0, violating condition 3.

This independent check confirms the equivalence and the co‑NP‑completeness of sorting‑network verification.