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 width n sorts all sequences of length m if it sorts all 2n binary sequences of length n.
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 [l0, l1,… ln-1] into [l0,… li-1, li↓lj, li+1,… lj-1, li↑lj, lj+1,… ln-1]. 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 : A → B, the pointwise extension map f : An → Bn maps a sequence [l0, l1,… ln-1]∈An to the sequence [f.l0, f.l1,… f.ln-1]∈Bn. Hence, the following
Lemma: comparator networks commute with the pointwise extension of monotonic functions
Let 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.l0, f.l1,… f.ln-1] = { defn. comparator box } [f.l0,… f.li-1, f.li ↓ f.lj, f.li+1,… f.lj-1, f.li ↑ f.lj, f.lj+1,… f.ln-1] = { lemma } [f.l0,… f.li-1, f.(li↓lj), f.li+1,… f.lj-1, f.(li↑lj), f.lj+1,… f.ln-1] = { defn. pointwise extension } map f.[l0,… li-1, li↓lj, li+1,… lj-1, li↑lj, lj+1,… ln-1] = { defn. comparator box } (map f ∘ [i ↕ j]).lFor the inductive case, a comparator network N can be decomposed as the composition of comparator networks NL and NR, such that:
N ∘ map f = { compositionality of network } (NL ∘ NR) ∘ map f = { associtativity of composition, base case } NL ∘ (map f ∘ NR) = { associtativity of composition, base case } map f ∘ (NL ∘ NR) = { 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∈An that is not sorted by N, that is, for m = N.l there is an 0 ≤ k < n-1 such that mk ≰ mk+1. For all c∈A, define f : A → {0, 1} as f.c = 1 if mk ≤ 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 } mk ≰ c ∧ mk ≤ c′ ≡ mk ≤ c ⇒ mk ≤ c′ ⇐ { transitivity ≤ } c ≤ c′Furthermore, f.mk = 1 and f.mk+1 = 0 which means that (map f ∘ N).l is unsorted. But since f is monotonic, by the second Lemma, (N ∘ map f).l is unsorted too. In other words, if there's a sequence over An that N doesn't sort, then there is a sequence over 2n 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