[CST-2] Kolmogorov complexity - cost of sorting

[Jonny Graham]

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)

HTH,
Jonny


Matej Pfajfar wrote:
> I can't really understand the ntes I made on the minimum cost of sorting
> proof that he did using kolmogorov complexity.
> 
> If you take a random permutation of N elements - than the string
> describing it this has K = nlog(n).
> 
> Now suppose you can sort in << nlog(n) comparisons.
> How do you then represent the string in less than nlog(n) bits?
> 
> Thanks,
> Matej
> 
> --
> Matej Pfajfar
> St John's College, University of Cambridge, UK
> 
> GPG Public Keys @ http://matejpfajfar.co.uk/keys
> WARNING: THIS E-MAIL ACCOUNT WILL BE DELETED ON
>          15/07/2002. PLEASE USE mp@cantab.net.
> 
> 
> 
> _______________________________________________
> 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 --