2008-07-09

The Zero-One Principle

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 aa′ such that:

aa′aaa′a′

Dually, the maximum of a, a′A is the unique element aa′ such that:

aaa′a′aa′

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

⟨∀a, a′A : aa′ : 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:

   aa′aaa′a′
⇒ { monotonicity of f }
   f.(aa′) ≤ f.a ∧ f.(aa′) ≤ f.a′
≡ {definition of ↓ }
   f.(aa′) = f.a ↓ f.a′

And dually for maxima.

Recall that an comparator box is a function (xy) = (xy, xy). Applied to a sequences, a comparator [ij] with 0 ≤ ij < n sorts elements i and j of [l0, l1,… ln-1] into [l0,… li-1, lilj, li+1,… lj-1, lilj, 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 : AB, the pointwise extension map f : AnBn 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 [ij]:

   ([ij] ∘ map f).l
= { defn. pointwise extension }
   [ij].[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.(lilj), f.li+1,… f.lj-1, f.(lilj), f.lj+1,… f.ln-1]
= { defn. pointwise extension }
   map f.[l0,… li-1, lilj, li+1,… lj-1, lilj, lj+1,… ln-1]
= { defn. comparator box }
  (map f ∘ [ij]).l

For 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 lAn that is not sorted by N, that is, for m = N.l there is an 0 ≤ k < n-1 such that mkmk+1. For all cA, define f : A → {0, 1} as f.c = 1 if mkc, and f.c = 0 otherwise. Now f is monotonic:

   f.c ≤ f.c′
⇐ { range of f }
   f.c = 0 ∨ f.c′ = 1
≡ { defn. f }
   mkcmkc′mkcmkc′
⇐ { transitivity ≤ }
    cc′

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:

Jim Apple said...

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

Matías Giovannini said...

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