[CST-2] Kolmogorov complexity - cost of sorting

[Jonny Graham]

Yes. You're right. I wrote a small program to wipe my HDD and, yes, I 
can't get it back ;-)
The inverse program *and* the steps [ which are <<nlog(n) ] that were 
taken in sorting would allow this to work. It's this that would be 
shorted than nlog(n) because the #steps in sorting is <<nlog(n) and the 
size of this program is negligent.

Hope that now makes more sense and is slightly less impossible.
Jonny

James Sutherland wrote:
> 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.
> 
> 
> 
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2


-- 
Jonny Graham
01223 565 373
07753 841 971

Selwyn College
Grange Road
Cambridge
CB3 9DQ

--My email account will cease to exist on 15/7/02--
--My new email address is jonnygraham@cantab.net --