[CST-2] Kolmogorov complexity - cost of sorting

[Matej Pfajfar]

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.