[CST-2] Kolmogorov complexity - cost of sorting

[Jonny Graham]

Yes, We are trying to prove that we can't sort faster than nlogn for 
arbitrary data.
nloglogn is faster than nlogn so yes, the argument (when fixed thanks to 
James...) would work. But since we can't sort faster than nlogn, we 
certainly can't sort faster than nloglogn anyway, so there's no problem.

The nlogn comes from the random permutation. Things can be arranged in 
n! ways which basically gives us a Kolmogorov complexity of nlogn 
(Stirling's approximation).



Jamie Shotton wrote:
> I seem to be missing something:  What exactly are we trying to prove?
> That we can't sort faster than nlogn for arbitrary data?  And in the
> argument below, what's to stop you substituting e.g. nloglogn for nlogn?
> AFAICS that makes no difference to the argument but gives a different
> result...?
> 
> Puzzled Jamie
> 
> 
>>>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)
>>
> 
> 
> 
> _______________________________________________
> 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 --