5 ms·
I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be com
by im3w1l 12y ago
I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.
- ac29 12y agoFrom the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
- bagels 12y agoThe challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.
- davmre 12y agoYes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression. There's a 1/32 chance they were all zeros, in which case you win. The difficult part is encoding the decompression procedure into a program of less than five bits. :-)
- martinko 12y ago>you'd need a method that can compress a random file with at least 2% ($100/5000) probability No, you'd need to be able to create a custom algo for that file with that probability. Quite a difference.
- davmre 12y agoThe "custom algorithm" thing is a red herring. You'll need to use some method to come up with your custom algorithm, once you see the input file, and whatever method you choose is itself a compression procedure, targeted at a fixed decoder which is essentially a Bash shell with a C compiler (* ). If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it's still impossible to reliably represent random data with fewer than the usual number of bits. (* ) There's a little bit of leeway here because the challenge as stated isn't actually precise about the execution environment. You could probably sneak in a small number of illicit bits by negotiating out-of-band whether the decompressor is to be a C program, ELF binary, Perl script, etc. It's not obvious how to make this useful though.
- function_seven 12y ago> If you intend to treat different inputs differently (e.g., "if it contains the string "AB", I'll use this algorithm, if it has more zeros than ones, I'll use this other one, etc"), this just means that your compression procedure contains some 'if' statements. The laws of information theory don't care whether your compression procedure is actually a computer program or just implicitly encoded into human actions; it's still impossible to reliably represent random data with fewer than the usual number of bits. While you're obviously correct about the information theory aspect of this, in this particular challenge, the contestant enjoys the privilege of pruning his decompressor to match just the one file. All the other "if" statements can be thrown away. So now a lossy algorithm can be used, that just happens not to be lossy on that one particular file.
- hurin 12y agoThe problem wasn't well formulated, since it didn't clearly define what can or cannot be done to the decompresser based on knowledge of the output file. But consider a more strongly formulated problem, where you must provide the decompresser and then a file is randomly selected to be put through it - as long as it's still a matter of compressing one particular file it is statistically possible to win (especially at $5000:$100) - The idea being that you can reinterpret data to make certain outputs cheaper while others more expensive.
- ikeboy 12y agoIt was well formulated; the whole point is that you can do whatever you want to the decompresser.
- yk 12y agoActually even that is not feasible: Assume that you split a m byte string into k byte decompressor and l byte input data. If k+l < m, that is you actually compress, then there are only 2^(k+l) possible output strings. And since sum_{i=0}^{m-1} 2^i = 2^m -1 there exists at least one string in the space of m character strings which can not be compressed by any algorithm.
- bagels 12y agoYes, knowing which string(s) to choose which have this property as the challenge giver is the hard part.
- a_e_k 12y agoFrom random.org, used as a source for the data: > RANDOM.ORG offers true random numbers to anyone on the Internet. The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.
- im3w1l 12y agoAh missed that. Yeah then it may be good enough randomness.
- emn13 12y agoBut yeah - it may well be not entirely random, and if someone actually managed to build a compressor based off any slight bias, I think they deserve the 5000 :-).
- path411 12y agoGive me a file the size of the universe, and my decompressor will re-sim the universe until the point of the file creation date and read the atmospheric noise from that point.
- tlrobinson 12y agoAren't cryptographically secure PRNGs supposed to produce outputs indistinguishable from truly random numbers?
- leni536 12y agoCSPRNG generated sequences can be trivially compressed. You just have to know the seed and the length to reproduce the sequence. However getting the seed from the sequence is unfeasible but theoretically possible by bruteforce.