9
$\begingroup$

I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The intent is to have a comparison network and sort numeric values. If I test 2^n values in this case 2^8. This is a lot of work|non-efficient way to test it. I'm looking for a mathematical model/proof to verify this is a valid sorting network. A sorting network based on insertion sort

$\endgroup$
  • 2
    $\begingroup$ What did you search, read , or try? What blocked you? The more precise the question, the better the answer. Is your question about any arbitrary comparison network, i.e. a general procedure to determine whether an arbitrary comparison network is a sorting network? Or is your question about the given disgram. $\endgroup$ – babou Jul 26 '15 at 11:23
  • 2
    $\begingroup$ You can use the zero one principle: a sorting network is correct if it works on all zero one inputs. $\endgroup$ – Yuval Filmus Jul 26 '15 at 12:39
  • $\begingroup$ @YuvalFilmus That is an exponential test (in number of inputs). Is it an NP complete problem.? $\endgroup$ – babou Jul 26 '15 at 14:23
  • $\begingroup$ @babou I have no idea. In this case it's practical. $\endgroup$ – Yuval Filmus Jul 26 '15 at 14:24
  • $\begingroup$ an obvious idea is an empirical approach, just consider its action on random permutations of [1..n], observe its result, either it will fail or succeed, if it succeeds you have a near-proof approach... $\endgroup$ – vzn Jul 26 '15 at 15:27
10
$\begingroup$

In general, verifying whether a particular comparison network is indeed a correct sorting network is a Co-NP complete problem. If you want to check by testing, then you need to try exponentially many tests.

In particular, there exist sorting networks that sort all but a single value correctly, so you can't hope to test whether the network is correct or not simply by feeding it a few inputs.

One standard method is to test whether it correctly sorts all $2^n$ inputs that are composed solely of zeros and ones. If it does, then it turns out that it will sort all inputs (even ones that aren't limited to zeros and ones). However, this requires exponentially many tests. Moreover, the number of tests cannot be reduced significantly: for zero-one inputs, it is possible to prove that at least $2^n-n-1$ tests are needed, to very that the sorting network is correct.

Alternatively, one can use tests where the inputs are permutations of $1,2,\dots,n$. This reduces the number of tests needed somewhat, but you still need exponentially many tests. In particular, $C(n, \lfloor n/2 \rfloor)-1$ tests are necessary and sufficient.

For proofs of these facts, see the following papers:

On the Computational Complexity of Optimal Sorting Network Verification. Ian Parberry. Parle'91 Parallel Architectures and Languages Europe, 1991.

Bounds on the size of test sets for sorting and related networks. Moon Jung Chung and B. Ravikumar. Discrete Mathematics, vol 81, pp.1--9, April 1990.

$\endgroup$
6
$\begingroup$

Quoting your question:

I'm looking for a mathematical model/proof to verify this is a valid sorting network.

While D.W.'s (excellent) answer deals with the general case, I will consider your specific example. A network of this form with $n$ inputs can be shown to be a sorting network by induction: (see image for illustration)

  1. $n=1$ input is always sorted;
  2. Assume that a network of size $n-1$ of this form is a sorting network, and consider a network of size $n$.
    1. The left-most "diagonal" will always correctly bring the largest element to the $n$-th position (in your case, $b_8$);
    2. You are left with a smaller, similar network with the remaining $n-1$ elements;
    3. This smaller network will sort all the remaining elements by the inductive hypothesis.

Proof illustration

$\endgroup$
5
$\begingroup$

When you look on a general sorting network, you might have no idea how to proof that it sorts every sequence of values (having the right length for the sorting network) correctly. But I've learned about this nice trick, how to simplify the task:

The 0-1-principle

When a sorting network sorts every sequence (with the right length) consisting only of "0" and "1" correctly, then it sort any sequence (with the right length) correctly. Of course "0" and "1" are placeholders for any distinct elements in the domain of the sorting network.

So you can construct a proof like this:

  1. Take two distinct elements from the domain of the sorting network and call them "0" and "1", so that "0" < "1"
  2. Construct all binary strings with the exact length of the sorting network
  3. In these strings substitute the 0-bit and the 1-bit with "0" and "1"
  4. Apply these strings to the sorting network
  5. Each string must be sorted to something like 000..01...1

Testing $2^n$ values

For an exhaustive test of a sorting network of length $n$ you usually would have to test all input combinations. But with the 0-1-principle you can bring this down to $2^n$ tests (testing all binary strings of length $n$).

Can we do it cheaper?

Unfortunately we probably can't get much cheaper than exhaustive testing, at least not when using a Turing machine to construct the proofs. Of course when you look an a specific sorting network, you might have a creative idea how to make a simple proof. But in general an algorithm for constructing such proofs is very likely as complex as testing all binary strings. The reason for this is that proofing sorting network is related to the NP complete complexity class as outlined in the other answers.

"Much cheaper" in this context means "polynomial time". It might be possible to find an algorithm that can do it "slightly" faster than exponential time but still needs more than polynomial time. See the comments for an example: Running in $2^{\sqrt n}$ steps is (slightly) faster than exponential time but still (much) slower than polynomial time.

Prospect / Outlook

Is your brain a Turing machine

A philosophical consequence is: When you believe that you can find a creative proof for the correctness of each sorting network, then you are also believing that you brain is very likely not a Turing machine.

Parallel sorting

The "0-1 principle" is also used to proof the correctness of parallel sorting algorithms. I have a (hopefully) nice presentation about this on Github.

Correcting the sorting network

If one of the strings is incorrectly sorted (so you have proven the sorting network wrong), you can use this to construct a sorting network without that bug. Just add an additional comparison on the position of the "1-0 border" in the wrong result string.

$\endgroup$
  • $\begingroup$ Nitpick: even if P!=NP, (co-)NP-completeness does not preclude the existence of sub-exponential algorithms, say with a runtime in $O(2^{\sqrt{n}})$. (Such algorithms exist for many NP-complete problems.) $\endgroup$ – Raphael Jul 27 '15 at 8:36
  • $\begingroup$ @Raphael If I get it right, P!=NP should only prohibit "polynomial" solutions for (co-)NP-complete problems, i.e. solutions where runtime (and memory usage) are bound by a polynomial term for arbitrary long inputs. So I only have to check if the term you have given is bigger than any polynomial for arbitrary big values of $n$. Right? $\endgroup$ – stefan.schwetschke Jul 27 '15 at 8:47
  • $\begingroup$ Something like that, yes. (I read your answer like "here's how to do it in exponential time, and we probably can't do better since it's co-NP-hard". That's a non-sequitur, hence my comment.) $\endgroup$ – Raphael Jul 27 '15 at 8:52

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.