Continuing my treatment of comparator networks, I've experimenting with the discovery of minimal sorting networks using evolutionary programming, about which I plan to write in the future. One of the things needed for that is a means of quickly evaluating if a given network actually sorts all sequences of a given length or not. There is a very powerful theoretical result, called the zero-one principle that aids in identifying sorting networks from general comparator networks. It says:

(The zero-one principle):A comparator network N of widthnsorts all sequences of lengthmif it sorts all 2^{n}binarysequences of lengthn.

The proof is not difficult, and is a good showcase for the equational reasoning I'm so fond of. First, some definitions.

Given an ordered set (**A**, ≤), the minimum of elements `a`, `a′` ∈ **A** is the unique element `a`↓`a′` such that:

a↓a′≤a∧a↓a′≤a′

Dually, the maximum of `a`, `a′` ∈ **A** is the unique element `a`↑`a′` such that:

a≤a↑a′∧a′≤a↑a′

A monotonic function from ordered set (**A**, ≤) to ordered set (**B**, ⊑) is a function that preserves orderings, that is:

⟨∀a,a′∈A:a≤a′: f.a⊑ f.a′⟩

With that, I can prove the first

Lemma:monotonic functions preserve minima (dually, maxima)Let f be monotonic on

A. Then ∀a,a′∈A, by definition of minimum:a↓a′≤a∧a↓a′≤a′⇒ { monotonicity of f } f.(a↓a′) ≤ f.a∧ f.(a↓a′) ≤ f.a′≡ {definition of ↓ } f.(a↓a′) = f.a↓ f.a′And dually for maxima.

Recall that an comparator box is a function (`x` ↕ `y`) = (`x`↓`y`, `x`↑`y`). Applied to a sequences, a comparator [`i` ↕ `j`] with 0 ≤ `i` ≤ `j` < `n` sorts elements `i` and `j` of [`l _{0}`,

`l`,…

_{1}`l`] into [

_{n-1}`l`,…

_{0}`l`,

_{i-1}`l`↓

_{i}`l`,

_{j}`l`,…

_{i+1}`l`,

_{j-1}`l`↑

_{i}`l`,

_{j}`l`,…

_{j+1}`l`]. A comparator network N is a sequence of such boxes, and as a sequence, it has a monoidal structure under composition. For a function f :

_{n-1}**A**→

**B**, the pointwise extension map f :

**A**

^{n}→

**B**

^{n}maps a sequence [

`l`,

_{0}`l`,…

_{1}`l`]∈

_{n-1}**A**

^{n}to the sequence [f.

`l`, f.

_{0}`l`,… f.

_{1}`l`]∈

_{n-1}**B**

^{n}. Hence, the following

Lemma:comparator networks commute with the pointwise extension of monotonic functionsLet f be monotonic on

A. By induction on the structure of N, we have for the base case a single comparator box [i↕j]:([i↕j] ∘ map f).l = { defn. pointwise extension } [i↕j].[f.l, f._{0}l,… f._{1}l] = { defn. comparator box } [f._{n-1}l,… f._{0}l, f._{i-1}l↓ f._{i}l, f._{j}l,… f._{i+1}l, f._{j-1}l↑ f._{i}l, f._{j}l,… f._{j+1}l] = { lemma } [f._{n-1}l,… f._{0}l, f.(_{i-1}l↓_{i}l), f._{j}l,… f._{i+1}l, f.(_{j-1}l↑_{i}l), f._{j}l,… f._{j+1}l] = { defn. pointwise extension } map f.[_{n-1}l,…_{0}l,_{i-1}l↓_{i}l,_{j}l,…_{i+1}l,_{j-1}l↑_{i}l,_{j}l,…_{j+1}l] = { defn. comparator box } (map f ∘ [_{n-1}i↕j]).lFor the inductive case, a comparator network N can be decomposed as the composition of comparator networks N

_{L}and N_{R}, such that:N ∘ map f = { compositionality of network } (N_{L}∘ N_{R}) ∘ map f = { associtativity of composition, base case } N_{L}∘ (map f ∘ N_{R}) = { associtativity of composition, base case } map f ∘ (N_{L}∘ N_{R}) = { compositionality of network } map f ∘ N

Now I can prove the

Theorem:The zero-one principle as stated above is valid.Suppose there is a sequence

l∈A^{n}that isnotsorted by N, that is, form= N.lthere is an 0 ≤k<n-1 such thatm≰_{k}m. For all_{k+1}c∈A, define f :A→ {0, 1} as f.c= 1 ifm≤_{k}c, and f.c= 0 otherwise. Now f is monotonic:f.c≤ f.c′⇐ { range of f } f.c= 0 ∨ f.c′= 1 ≡ { defn. f }m≰_{k}c∧m≤_{k}c′≡m≤_{k}c⇒m≤_{k}c′⇐ { transitivity ≤ }c≤c′Furthermore, f.

m= 1 and f._{k}m= 0 which means that (map f ∘ N)._{k+1}lis unsorted. But since f is monotonic, by the second Lemma, (N ∘ map f).lis unsorted too. In other words, if there's a sequence overA^{n}that N doesn't sort, then there is a sequence over2^{n}that N doesn't sort either; by contrapositive the theorem follows.

In the next post I'll show how this translates in an efficient test for comparator networks.

## 2 comments:

I'm sure you already know about Much Ado About Two.

No I didn't! Thank you so much for the link.

Post a Comment