←back to thread

The $5000 Compression Challenge (2001)

(www.patrickcraig.co.uk)
181 points ekiauhce | 1 comments | 23 Nov 24 21:10 UTC | HN request time: 0s | source
Show context
benchmarkist ◴[24 Nov 24 00:08 UTC] No.42224932[source]▶
Take random bytes from /dev/urandom, encrypt it. There is no way any compressor can reduce the size of that file. I'm pretty sure there is no way the second player can win this game. Actually, the encryption part isn't even necessary. There is no compressor that can reduce the size of a random stream of bytes.
replies(3): >>42225052 #>>42225062 #>>42225454 #
cortesoft ◴[24 Nov 24 00:34 UTC] No.42225052[source]▶
There is no general purpose compressor that can achieve compression on all random streams of bytes... but there is a possibility to compress a specific random stream of bytes, if you get lucky
replies(1): >>42225079 #
lambdaone ◴[24 Nov 24 00:38 UTC] No.42225079[source]▶
Absolutely! Can this probability be quantified?
replies(1): >>42225186 #
1. benchmarkist ◴[24 Nov 24 01:02 UTC] No.42225186[source]▶
You'd have to define what you mean by luck which would be equivalent to choosing some pattern that your compressor can recognize in a random stream of bytes and then computing the probability that pattern appeared in some random byte sequence. It's not a winnable game in any practical sense because whatever compressor you choose the probability of getting a sequence from your opponent that will conform to the patterns recognizable by your compressor is essentially 0.