[CST-2] Kolmogorov complexity - cost of sorting

[James Sutherland]

On Fri, 31 May 2002, Jonny Graham wrote:

> Imagine we could create a program (constant Kolmogorov complexity) which
> sorts in less than nlog(n).
> Consider the *inverse* of this program (still constant) which takes a
> sorted list and outputs it in the original random ordering in less than
> nlog(n)
> This would allow us to compress the original random permutation as the
> sorted bits + progran(constant).
> But since it was a *random* permutation, it's uncompressible!
> Contradiction -- so we can't sort in less than nlog(n).
>
> This ignores the size of the constant of the program, but it still works
> if you include that. (Basically, the program would need to be able to
> sort in <<nlog(n)-c)

It's the INVERSE sort which doesn't exist, though. Otherwise, using this
logic:

1. Take a program which wipes your HDD.
2. Take the inverse of this program, which puts the contents of your HDD
back.
3. You have compressed the whole of your HDD into one small program!

Hence, it is EITHER impossible to wipe your HDD, OR it is impossible to
UNwipe it. Clearly, it's the latter.

In the sorting case, by sorting the input, you are removing information
(the original ordering). Just like "replace the first value with 1", this
operation is not reversible without knowing the original value you
removed...


James.