Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

For sorting networks, the 0-1 principle says that if it can sort any sequence of 0's and 1's, then it can sort any list.

What if I want to build a comparison-swap network for merging two pre-sorted lists. Can I still rely on the 0-1 principle to determine if my network is correct?

Note: If so, this means it's possible to determine whether a network is a merging network in polynomial time (since there are only polynomially-many pairs of sorted lists of zeros and ones)

share|improve this question

1 Answer 1

up vote 10 down vote accepted

$\def\et{\mathbin\&}$Yes, and this holds much more generally. Note that a comparator can be thought of as a pair of gates, one of which computes $\min\{x,y\}$, and the other $\max\{x,y\}$. A linearly ordered set is a distributive lattice with $x\land y=\min\{x,y\}$ and $x\lor y=\max\{x,y\}$. We have the following 0–1 principle:

Let $C$ be a circuit with $\land$ and $\lor$ gates, and $\phi(u_1,\dots,u_n)$ a property of values of nodes of $C$ expressible as a conjunction of quasi-identities in the language of lattices (i.e., implications of the form $t_1=s_1\et\dots\et t_k=s_k\to t_0=s_0$, where $t_i$ and $s_i$ are terms using $\land$, $\lor$, and the variables $u_j$).

If $\phi(u_1,\dots,u_n)$ holds whenever $C$ is evaluated in the $\{0,1\}$ lattice, then it holds whenever $C$ is evaluated in an arbitrary distributive lattice.

This is an immediate consequence of the facts that the $2$-element lattice generates the quasivariety of distributive lattices (i.e., every distributive lattice can be embedded in a direct product of $2$-element lattices), and that values of nodes of $C$ are lattice terms in values of the input variables.

Note that $t\le s$ is equivalent to $t\land s=t$, hence we can freely use inequalities instead of equalities in the statement above.

Now, if $C$ is a comparator network with inputs $x_1,\dots,x_n,y_1,\dots,y_n$ and outputs $z_1,\dots,z_{2n}$, it automatically computes a permutation of the inputs, hence the property that it correctly merges sorted lists can be expressed by the conjunction of the quasi-identities $$x_1\le x_2\et\dots\et x_{n-1}\le x_n\et y_1\le y_2\et\dots\et y_{n-1}\le y_n\to z_i\le z_{i+1}$$ for $i=1,\dots,2n-1$, hence if it works for $0$–$1$ inputs, it also works over arbitrary linearly ordered sets.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.