[8398] in cryptography@c2.net mail archive
Re: Cryptographic Algorithm Metrics
daemon@ATHENA.MIT.EDU (lcs Mixmaster Remailer)
Mon Jan 8 14:57:26 2001
Date: 7 Jan 2001 01:40:11 -0000
Message-ID: <20010107014011.10506.qmail@nym.alias.net>
To: cryptography@c2.net
From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu>
Burton Rosenberg writes:
> There is the concept of Kolomogorov complexity, the size of the
> smallest algorithm that can generate the message. A perfectly
> compressed message would have Kolomogorov complexity
> equal to itself.
>
> Kolomogorov complexity does have a freedom in its definition,
> but the exciting thing is that any two definitions will differ only
> by a constant.
Yes, the freedom is that the complexity is defined only with respect to a
particular Universal Turing Machine. For any given string you can find
a UTM which compresses it as small as you like, down to a single bit.
This makes it useless as an "absolute" definition of complexity in the
present context. (Also as Nick Szabo pointed out it is uncomputable
due to the halting problem.)
