[CST-2] Kolmogorov complexity - cost of sorting

[Alan Lawrence]

Sort the permutation, and on each comparison made by your sorting 
algorithm, output a 0 or 1 according to whether one element was less 
than or greater than the other. If you can sort with less than nlog(n) 
comparisons, you have output less than nlog(n) bits, and this is enough 
to perform the "reverse sort" and recover the permutation.

HTH
--Alan

On Friday, May 31, 2002, at 12:57  pm, 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