<p><span class="math-container">$\def\et{\mathbin\&amp;}$</span>Yes, and this holds much more generally. Note that a comparator can be thought of as a pair of gates, one of which computes <span class="math-container">$\min\{x,y\}$</span>, and the other <span class="math-container">$\max\{x,y\}$</span>. A linearly ordered set is a distributive lattice with <span class="math-container">$x\land y=\min\{x,y\}$</span> and <span class="math-container">$x\lor y=\max\{x,y\}$</span>. We have the following 0–1 principle:</p>
<blockquote>
<p>Let <span class="math-container">$C$</span> be a circuit with <span class="math-container">$\land$</span> and <span class="math-container">$\lor$</span> gates, and <span class="math-container">$\phi(u_1,\dots,u_n)$</span> a property of values of nodes of <span class="math-container">$C$</span> expressible as a conjunction of quasi-identities in the language of lattices (i.e., implications of the form <span class="math-container">$t_1=s_1\et\dots\et t_k=s_k\to t_0=s_0$</span>, where <span class="math-container">$t_i$</span> and <span class="math-container">$s_i$</span> are terms using <span class="math-container">$\land$</span>, <span class="math-container">$\lor$</span>, and the variables <span class="math-container">$u_j$</span>).</p>
<p>If <span class="math-container">$\phi(u_1,\dots,u_n)$</span> holds whenever <span class="math-container">$C$</span> is evaluated in the <span class="math-container">$\{0,1\}$</span> lattice, then it holds whenever <span class="math-container">$C$</span> is evaluated in an arbitrary distributive lattice.</p>
</blockquote>
<p>This is an immediate consequence of the facts that the <span class="math-container">$2$</span>-element lattice generates the quasivariety of distributive lattices (i.e., every distributive lattice can be embedded in a direct product of <span class="math-container">$2$</span>-element lattices), and that values of nodes of <span class="math-container">$C$</span> are lattice terms in values of the input variables.</p>
<p>Note that <span class="math-container">$t\le s$</span> is equivalent to <span class="math-container">$t\land s=t$</span>, hence we can freely use inequalities instead of equalities in the statement above.</p>
<p>Now, if <span class="math-container">$C$</span> is a comparator network with inputs <span class="math-container">$x_1,\dots,x_n,y_1,\dots,y_n$</span> and outputs <span class="math-container">$z_1,\dots,z_{2n}$</span>, 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
<span class="math-container">$$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}$$</span>
for <span class="math-container">$i=1,\dots,2n-1$</span>, hence if it works for <span class="math-container">$0$</span>–<span class="math-container">$1$</span> inputs, it also works over arbitrary linearly ordered sets.</p>

CC BY-SA 3.0
2014-08-10T11:06:30.757Z
2014-08-10T11:06:30.757Z
2020-06-17T09:38:08.363Z
Emil Jeřábek
<p>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.</p>

<p>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?</p>

<p>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)</p>

<sorting-network>
Does the 0-1 principle apply to merge networks?
dspyz
# Does the 0-1 principle apply to merge networks?

(Asked by: username_0 on 2014-08-10)

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)

**Tags:** sorting-network


---

## 1 answers

### Answer by username_1 on 2014-08-10. Score: 11 | Accepted answer

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


---

