# Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

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

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

• 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 Mar 2 '15 at 2:39
• @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 Mar 2 '15 at 6:29

It seems not. Ian Parberry makes reference 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$.
• 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 Mar 3 '15 at 1:14
• 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. Mar 3 '15 at 1:19
• More sleuthing: "Strong nondeterministic Turing reduction — a technique for proving intractability" (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. Mar 3 '15 at 1:23