6
$\begingroup$

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)

$\endgroup$
11
$\begingroup$

$\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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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