2 Refined statement about runtime
source | link

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.

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

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.

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.

1
source | link

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

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.