[CST-2] Off topic.

[Matej Pfajfar]

I hate to be a party breaker but does this have to do a lot with revision?

The "inverse sort" he was talking about is that you take your sorting
program, replace "if (a<b)" with "if (next_input_bit() == 1)" and you get
a program than can output a permutation of n bits.
So if the original program can sort any string, it can output ANY
permutation.

So you can represent the string with nlogn - C + c' bits where nlogn - C
is the number of comparisons the sorting program makes.
But all this has to be equal to nlog (n) bits because the original string
can't be compressed.

??

--
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.