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)$.
Is it enough to sort for polynomially many 0-1 sequences for a sorting network?
ds.algorithms;sorting;sorting network
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$.