<p>It seems not.  <a href="https://larc.unt.edu/ian/pubs/snverify.pdf">Ian Parberry makes reference</a> to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further deduce that the problem of verifying a sorting network is $co$-$NP$ complete.  I can't find the original paper right away, but certainly it matches (my) intuition.</p>

<p>Edit to add: It is actually very easy to find such a network that misses exactly one string.  The string to be missed will be $(1,0,\ldots,0)$.  Now you just want a circuit that sorts the last $n-1$ bits, then sorts the first $n-1$ bits.  This circuit will sort anything with at least two $1$s, will obviously sort the all-zero string, and will sort any string starting with $0$.</p>

CC BY-SA 3.0
2015-03-03T01:05:12.417Z
Can the example sorting network in your answer be generalized, so that for any given string, you can construct a sorting network that mis-sorts that string?  You show how to do it for one particular string, but what about other strings?
D.W.
CC BY-SA 3.0
2015-03-03T01:14:04.940Z
You can definitely do it for any string of weight $1$ or $n-1$, but I doubt it is possible to miss a single arbitrary bitstring.
Andrew D. King
CC BY-SA 3.0
2015-03-03T01:19:01.650Z
OK, so I'm not seeing how your answer shows that the answer is "No". The construction in the second paragraph of your answer doesn't imply a negative answer to the original question, as there are only polynomially many strings of weight $1$ or $n-1$.  It seems all the work in your answer is being done by the reference in the Ian Parberry paper, but that sentence in the Parberry paper is rather vague and without reading the Chung et al paper I'm not seeing how we can conclude that the answer to the question is "No".
D.W.
CC BY-SA 3.0
2015-03-03T01:23:37.303Z
I see your point and I agree.  I actually misparaphrased Parberry, who says *they further deduce* (that the problem is $co$-$NP$-complete).  So maybe the proof of $co$-$NP$-completeness is more involved than I first assumed.
Andrew D. King
CC BY-SA 3.0
2015-03-03T01:23:40.930Z
More sleuthing: "[Strong nondeterministic Turing reduction — a technique for proving intractability](http://dx.doi.org/10.1016/0022-0000(89)90017-2)" (Chung & Ravikumar) lists the following as Lemma 2.1: given any non-sorted string $x$, there exists a sorting network of polynomial size that sorts all strings correctly except $x$.  For the proof it refers to "On the size of test sets for sorting and related problems" (Chung & Ravikumar), but I can't seem to find a copy of the latter paper.  This would indeed imply that the answer to this question is "No".
D.W.
CC BY-SA 3.0
2015-03-03T10:52:51.223Z
[Paper by Chung & Ravikumar](http://www.researchgate.net/profile/Bala_Ravikumar4/publication/220194594_Bounds_on_the_size_of_test_sets_for_sorting_and_related_networks/links/546a620c0cf2397f7830181e.pdf)
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2015-03-03T00:45:07.427Z
2015-03-03T01:24:26.690Z
2015-03-03T01:24:26.690Z
Andrew D. King
<p>The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers.
Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence from S, then it sorts every 0-1 sequence and the size of $S$ is polynomial in $n$?</p>

<p>For example, if $S$ consists of all sequences where there are at most $2$ runs (intervals) of 1's, then is there a sorting network N and a sequence that is not ordered by N if all members of $S$ are ordered by N?</p>

<p><strong>Answer:</strong> As can be seen from the answer and the comments to it, the answer is that for every unsorted string there is a sorting network that sorts every other string.
A simple proof for this is the following.
Let the string $s=s_1\ldots s_n$ be such that $s_i=0$ for ever $i&lt;k$ and $s_k=1$.
Since $s$ is unsorted, after sorting $s_k$ should be $0$.
Compare $k$ with every $i$ for which $s_i=1$.
Then compare every pair $(i,j)$ such that $i\ne k$ and $j\ne k$ many times.
This leaves the whole string sorted, except possibly for $s_k$, which is unsorted for $s$, and for certain other strings that have more $1$'s than $s$.
Now compare $s_k$ for $i=n$ downto $1$ except for the place where $s_k$ should go in $s$.
This will sort everything but $s$.</p>

<p><strong>Update:</strong> I wonder what happens if we restrict the depth of the network to $O(\log n)$.</p>

CC BY-SA 3.0
2015-03-02T02:39:48.640Z
It seems that to be possible you must restrict the size of the sorting network to be smaller than the size of $S$. Otherwise, couldn't the network just check if the input is one of the elements of $S$ and act correctly if so, otherwise act incorrectly?
usul
CC BY-SA 3.0
2015-03-02T06:29:43.713Z
@usul: I don't think a sorting network can check such a thing. Anyhow, it is only natural to work with sorting networks whose size is polynomial in $n$.
domotorp
<ds.algorithms><sorting><sorting-network>
Is it enough to sort for polynomially many 0-1 sequences for a sorting network?
domotorp
# Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

(Asked by: username_0 on 2015-03-01)

The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers.
Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence from S, then it sorts every 0-1 sequence and the size of $S$ is polynomial in $n$?

For example, if $S$ consists of all sequences where there are at most $2$ runs (intervals) of 1's, then is there a sorting network N and a sequence that is not ordered by N if all members of $S$ are ordered by N?

**Answer:** As can be seen from the answer and the comments to it, the answer is that for every unsorted string there is a sorting network that sorts every other string.
A simple proof for this is the following.
Let the string $s=s\_1\ldots s\_n$ be such that $s\_i=0$ for ever $i

**Update:** I wonder what happens if we restrict the depth of the network to $O(\log n)$.

**Tags:** ds.algorithms, sorting, sorting-network

> **Comments:**
> **username_1**: It seems that to be possible you must restrict the size of the sorting network to be smaller than the size of $S$. Otherwise, couldn't the network just check if the input is one of the elements of $S$ and act correctly if so, otherwise act incorrectly?  
> **username_0**: @username_1: I don't think a sorting network can check such a thing. Anyhow, it is only natural to work with sorting networks whose size is polynomial in $n$.  

---

## 1 answers

### Answer by username_2 on 2015-03-03. Score: 8 | Accepted answer

It seems not. [Ian Parberry makes reference](https://larc.unt.edu/ian/pubs/snverify.pdf) to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further deduce that the problem of verifying a sorting network is $co$-$NP$ complete. I can't find the original paper right away, but certainly it matches (my) intuition.

Edit to add: It is actually very easy to find such a network that misses exactly one string. The string to be missed will be $(1,0,\ldots,0)$. Now you just want a circuit that sorts the last $n-1$ bits, then sorts the first $n-1$ bits. This circuit will sort anything with at least two $1$s, will obviously sort the all-zero string, and will sort any string starting with $0$.

> **Comments:**
> **username_3**: Can the example sorting network in your answer be generalized, so that for any given string, you can construct a sorting network that mis-sorts that string?  You show how to do it for one particular string, but what about other strings?  
> **username_2**: You can definitely do it for any string of weight $1$ or $n-1$, but I doubt it is possible to miss a single arbitrary bitstring.  
> **username_3**: OK, so I'm not seeing how your answer shows that the answer is "No". The construction in the second paragraph of your answer doesn't imply a negative answer to the original question, as there are only polynomially many strings of weight $1$ or $n-1$.  It seems all the work in your answer is being done by the reference in the Ian Parberry paper, but that sentence in the Parberry paper is rather vague and without reading the Chung et al paper I'm not seeing how we can conclude that the answer to the question is "No".  
> **username_2**: I see your point and I agree.  I actually misparaphrased Parberry, who says *they further deduce* (that the problem is $co$-$NP$-complete).  So maybe the proof of $co$-$NP$-completeness is more involved than I first assumed.  
> **username_3**: More sleuthing: "[Strong nondeterministic Turing reduction — a technique for proving intractability](http://dx.doi.org/10.1016/0022-0000(89)90017-2)" (Chung & Ravikumar) lists the following as Lemma 2.1: given any non-sorted string $x$, there exists a sorting network of polynomial size that sorts all strings correctly except $x$.  For the proof it refers to "On the size of test sets for sorting and related problems" (Chung & Ravikumar), but I can't seem to find a copy of the latter paper.  This would indeed imply that the answer to this question is "No".  
> **username_4**: [Paper by Chung & Ravikumar](http://www.researchgate.net/profile/Bala_Ravikumar4/publication/220194594_Bounds_on_the_size_of_test_sets_for_sorting_and_related_networks/links/546a620c0cf2397f7830181e.pdf)  

---

