5 ms·

The $5000 Compression Challenge

42 points by igul222 14y ago

SparrowOS 14y ago
I did Ticketmaster's file compression. Denny gave me a magazine with LZW. I screwed-around with many good ideas to combine with LZW, but that was just a white-trash waste of time. I had the sense to keep it simple, in the end, with straight-up LZW.
kunil 14y ago
I don't get it, why he didn't just write a simple algorithm and get the prize? It looks like an easy money
- CJefferson 14y ago
  You mean, why didn't he write a simple compression algorithm which actually shrunk the data? The short answer is, it was (almost certainly) impossible. You cannot compress random data. The only reason files you compress normally seem to compress is almost every file you come across normally contains some structure and therefore some redundancy.
  - kunil 14y ago
    It is not random, input file is constant. Surely you can write an algorithm to compress a specific file.
    - ghshephard 14y ago
      But the sum of your decompression program and compressed file would then be larger than the original data file.
      - haberman 14y ago
        Mike's contest didn't limit the total size of the (input, random) data file, so you could make it arbitrarily large to make the cost of the decompression program arbitrarily small.
        aes256 14y ago
        > [...] the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state.
        ghshephard 14y ago
        If the data file is truly random, then there is no decompression program + compressed file that would be smaller than the original random file. That's the entire point.
        haberman 14y ago
        I'm not saying you could! I am only rebutting your earlier line of reasoning. IF you could write an algorithm that would compress a specific block of random data by any non-zero percentage, and IF you can make the original random data arbitrarily large, THEN the overall size of the code to implement this algorithm would not matter, because you could amortize it over an arbitrarily large random data file. However I am not claiming that such an algorithm to compress a specific block of random data exists! However other people are arguing that this is indeed theoretically possible: http://news.ycombinator.com/item?id=5025527 http://news.ycombinator.com/item?id=5025527
        cncool 14y ago
        What if the rng generates a file with massive redundancy by chance. Doesn't make it any less "truly random."
        ozgung 14y ago
        Then how would you find redundancy in arbitrarily large random data?
        ars 14y ago
        See my comment http://news.ycombinator.com/item?id=5025527 http://news.ycombinator.com/item?id=5025527 This is a misunderstanding of the pigeonhole principle, which only applies to a specific compression algorithm. It does NOT apply if you get to write a custom algorithm for this data set. There are always redundancies in random data. If you can pick them out ahead of time with a custom algorithm it's certainly possible to "compress" it. Edit: I think I may be wrong here.
CJefferson 14y ago
This is an old story, but a fun one. To me it is clear that Mike Goldman should have paid up. Patrick clearly completed the challenge placed on him. While Patrick didn't obey the spirit of the challenge he obeyed the law, and Mike knew full well that the spirit of his challenge was impossible!
- emn13 14y ago
  Also, I'm not sure it was very wise of Mike to assume the data was truly incompressible. It's unlikely someone would manage to compress it (certainly for just 5k), but if you truly believe you have a source for billions or trillions of bits and that those bits then have exactly 100% as much entropy - well, you're taking a lot on faith. Indeed the fact that the content length was preselected implies some amount of regularity that might be (abused). Oh well.
- emn13 14y ago
  I don't agree - Patrick was (ab)using the discrepancy between file content size and file store size. For a single compressed file this may not be very relevant (hence its omission in the original problem description), but the changed rules proposed by patrick also didn't address it. As the designer of those new rules it was his responsibility to be clear, particularly since he was intending to use that discrepancy to his advantage. Yeah, Mike was stupid and not exactly nice - but that doesn't mean Patrick wasn't too.
vanni 14y ago
Previous discussion: http://news.ycombinator.com/item?id=4616704 http://news.ycombinator.com/item?id=4616704
Nate75Sanders 14y ago
Mike Goldman does not need to ever issue a challenge again. It is WIDELY agreed upon by people who engage in this activity regularly (known as "prop betting") that the spirit of the law does not matter one bit. He was way out of his element here and Patrick was well within his rights to do what he did.
- dustyleary 14y ago
  A great set of stories from an amazing life: http://www.amazon.com/Amarillo-Slim-World-Full-People/dp/B000GG4GS0 http://www.amazon.com/Amarillo-Slim-World-Full-People/dp/B00... Amarillo Slim engaged in these sort of prop bets all the time. Some of the more interesting stories where he "abuses the rules": * He bet that he could hit a golf ball a mile, "as long as bounces and rolls are allowed... flat ground of course"... When the wager was accepted, he teed off at a frozen pond, where it wasn't that difficult to accomplish. * Two variations on beating a champion at their own game: - Slim played Minnesota Fats at pool, "as long as I can provide the cue sticks"... And then beat Fats when they both had to play with broomsticks instead of real pool cues. - Slim bet that he could beat a very good ping pong player, "as long as I get to pick the rackets"... When the wager was accepted, Slim brought two identical cast iron skillets and let his opponent pick which "racket" he wanted. Without having practiced, his opponent didn't stand a chance. -- Later, someone else approached Slim and wanted to do the same bet. They had heard of the original bet, and had an Asian pingpong champion "ringer". (It seems pitifully obvious to me that Slim wouldn't pull the same trick after the story was out, but apparently this gambler had his Asian ringer practice with a skillet and thought he would be "safe")... For the second bet, Slim used "standard" Coca-Cola bottles, and won again.
- SatvikBeri 14y ago
  I love working with people like Patrick. In business, it's really easy to get caught up with assumptions, and come up with a design that does X, Y, and Z when all you really need is X. It's the people who're good at thinking outside the box and looking at the letter of the law, so to speak, who can take a step back and say "all we really need is X."
xentronium 14y ago
Why even bother with file concatenation? Just use 3M chars long filename for an empty file to "compress" 3Mb of data.
- jlgreco 14y ago
  DOS I assume.
ars 14y ago
The pigeonhole principle only applies to a specific compression algorithm. If you get to custom write the algorithm for the data you can arrange things so that for this datafile it will be smaller, yet larger for any other file, and still meet the principle. i.e. this is not actually impossible. If you can find ANY redundancy in the data, and you can code a very small decompresser specifically for that, you can probably win. And due to the nature of randomness, there are always numeric streaks, and other patterns in the data. The larger the datafile the better the chance of finding some sort of pattern or streak. The decompresser does not have to be large either - it would be perfectly legal to use a perl script for example. (i.e. so you don't have to use space writing IO handling code). Edit: I suspect I may be wrong here.
- jgeralnik 14y ago
  No. Let's say you have a file of size X. You want to write a program of size Y which will decompress an X-Y-1 sized file back to the original program. Does such a program and file exist for every file of size X? Using the pigeon hole principle, we can see that it does not. There are 2^X files of size X, but only 2^(X-1) inputs of length Y+X-Y-1. Therefore, not every file can be compressed this way. It doesn't matter what your decompressor is written in or how, you still can't do it.
  - ars 14y ago
    I see your point.
  - czr80 14y ago
    This is correct for the general case, but I think his argument is that for any specific file you can (almost certainly) find some redundancy and so find an algorithm to compress that specific file.
    - ars 14y ago
      That is exactly my argument. But now I think I'm wrong because what if you take the new data (i.e. the decompressor plus the compressed data), and try to compress that.
haberman 14y ago
Poetic justice. I love this quotation from Mike: "I think that I did not make a mistake except to believe that you truly intended to attempt to compress the data I was sending you." Mike is happily preying upon people by taking their money to enter what he believes is an impossible contest, but the moment he is outsmarted he appeals to morals and calls into question whether Patrick was acting honestly. I'm guessing there is some backstory on this newsgroup involving people who would claim to invent compression algorithms that do the impossible. I'm imagining that one day Mike thought "time to get these people to put their money where their mouth is." Still, it's pretty low to pose the challenge without saying "I'm taking this bet because it's highly unlikely that you can actually succeed. This is explained in the FAQ. Are you sure you want to give me $100?"
- deleted 14y ago
  [deleted]
- jlgreco 14y ago
  I am reminded of "apocalypse loans". (loans that only need to start being paid back, usually with incredibly steep interest, after an apocalypse that the borrower is anticipating. "If the world ends, you pay nothing!") I've seen such loans proposed often, but I don't know if anyone has ever actually taken one.
  - ars 14y ago
    It exists: https://www.google.com/search?q=rapture+pet+care https://www.google.com/search?q=rapture+pet+care
- svantana 14y ago
  Actually, it is most likely possible, it's just very difficult. For example, it is likely that the data file was generated using a deterministic computer program. And that program is most likely a lot smaller than the outputted data. Therefore, one could use that very program as the "decompressor" - voila! The problem is - it would take astronomical computational resources to recreate that program, although there is a very straightforward algorithm to find it - just test out all possible programs starting from 0,1,2,3, and so on...
pavanky 14y ago
Makes me wonder if a "decompressor" adding generating hundreds of decompressed files by brute force (of which the original file is one) would be a valid solution. You could store a certain section of the original as the "compressed file"
algorias 14y ago
Even without doing any filesystem tricks, the challenge seems quite possible. While it's true that writing a compressor that compresses all input data is impossible, this barrier is removed because the compressor only needs to work on a single file.
- praptak 14y ago
  But the "decompressor" here is also more or less fixed - it's the environment in which the challenger program needs to run. So, the organizer of the challenge would need to be unlucky to pick a file that is compressible for this particular decompressor. Mathematically this has non-zero (albeit very small) probability but I'd wager that even having such file it would be unfeasible to find its compressed form. Maybe the file is the third million of bytes of pi squared, but how do you find this fact?
- UnoriginalGuy 14y ago
  But you're forgetting what the challenge actually is. It is file+decompressor < input. So by the very nature of it if your decompressor is non-zero in length, you have to find some efficiency/tricks to make the file smaller. Realistically the overhead on the decompressor will be 10 KB and that is before any kind of actual logic, so you are looking at shaving a minimum of 50 KB off of the original file (which is completely random).
  - algorias 14y ago
    I'm not forgetting that. It's just that any specific random file will have (with high probability), patterns that can be exploited. It's not guaranteed to work on all files of course. The theoretical limit (per bijection argument) is that at most half the strings of length n can be losslessly represented in strings of length n-1, because there are half as many strings of length n-1 than of length n. So if, for example, 2% of files can actually be reduced in size (I don't know what the actual number is, and if it is even computable) that's still positive EV in a $100 vs $5000 bet.
    - jgeralnik 14y ago
splicer 14y ago
Just post the original data file on the web, then have your "decompression" program download the file. The "compressed" file could simply contain a URL.
splicer 14y ago
Here's another approach: Let the compressed file contain a hash (say, SHA1) of the original file. The decompression program then generates random files of the chosen size. If a generated file's hash doesn't match the desired hash, delete it. Now run the program for a very long time. The program is likely to eventually reproduce the original file (along with a bunch of files that happen to have the same hash), and you win :)
- shubhamjain 14y ago
  Would complete in perhaps just a couple of billions of years. :)
  - UnoriginalGuy 14y ago
    But the rules didn't say the file had to be massive. You get to pick the size, so pick 100 Kb or similar. That would still take forever...
    - deleted 14y ago
      [deleted]
- Beltiras 14y ago
  Let's say you have a file of size n and a hash of size log(n). This means you have n/log(n) collisions (matches). I made a similar suggestion on another HN thread linking that same story (I suggested using two radically different hashing functions, one hash result would not necessarily have an evenly distributed result from the other hashing function when you vary the plaintext). Even while posting I thought that I must be wrong, I just didn't feel wrong about it. Now I do.
  - splicer 14y ago
    The purpose of using a hash is just to avoid running out of disk space. With enough disk space, you don't even need to hash/delete files.
- 14y ago
deleted 14y ago
[deleted]
RyanZAG 14y ago
It is definitely possible to win this challenge though. Consider an arbitrary long series of integers. Somewhere within this series of integers, there will be some kind of randomly created pattern, since this is a property of an infinite set. eg. somewhere within the data set, there could be the values [1, 2, 3, ... 10] or [1, 3, 9, .. 27] or [1, 2, 4, 16, 32] - it does not matter which of these patterns, exist, only that there does exist some mathematical pattern in the data. The chances of there being no pattern in a big enough set of random data is impossible as there is a finite number of possible data combinations for bytes [1..256][1..256] etc. I guess a data set of 256^256 bytes would guarantee a pattern, but I'm sure there is a far smaller number that would give 99% confidence. Once you find a pattern in the data, you can remove that pattern and replace it with code that will recreate the pattern using a data offset. ie. you remove the pattern from the data completely, and replace it with a smaller piece of code to recreate that pattern exactly and insert it into the correct position. The key here is that once the data has been generated, it is no longer 'random data', but a fixed input. eg, you cannot compress a random unknown string of bytes, but you can compress the string [1,2,4,16..] The output data would have all possible mathematical patterns removed from it, and the decompression code would be just a list of mathematical functions and data offset points.
- lifthrasiir 14y ago
  You are recreating Kolmogorov complexity there. Kolmogorov complexity is defined as the minimal amount of program (for some programming language) to recreate the given string. By the definition, your strategy will compress the data no better than its Kolmogorov complexity. In this aspect, Kolmogorov complexity measures the data's true randomness. If the random data has been generated correctly its complexity should be near its length, however, so your strategy won't work. (And there is enough evidence that this was the case.) It does not matter whether the data is already known or not; it is the data's inherent randomness prohibiting you to compress it. To be sure, of course, Patrick Craig did not compress it in the pure information theoretic sense. Mike Goldman failed to equate the goal to that information theoretic compression however.
  - RyanZAG 14y ago
DanBC 14y ago
If you're interested in efficient compression with English you might like the Hutter Prize (http://prize.hutter1.net/ http://prize.hutter1.net/) - a €50,000 prize if you can compress the 100MB file enwik8 to less than the current record of about 16MB. They claim it's an AI problem. I guess it could be if you're compressing a bunch of different English texts, but this challenge has a single text. A program that provides very efficient compression of this text might not be so great for other texts. Mike's challenge took a specially selected random file. As other people said, this was an attempt to show compression kooks that some files are not compressible (if you include the size of the decompressor).
kyle4211 14y ago
I can't find anything which solidly points to this challenge being 'likely' impossible. This all is not so simple as pointing at Kolmogorov complexity. Randomness is not so much inherent as relative to the machine on which you're running your program. http://rjlipton.wordpress.com/2011/06/02/how-powerful-are-random-strings/ http://rjlipton.wordpress.com/2011/06/02/how-powerful-are-ra...

42 points by igul222 14y ago

I did Ticketmaster's file compression. Denny gave me a magazine with LZW. I screwed-around with many good ideas to combine with LZW, but that was just a white-trash waste of time. I had the sense to keep it simple, in the end, with straight-up LZW.

kunil 14y ago

I don't get it, why he didn't just write a simple algorithm and get the prize? It looks like an easy money

CJefferson 14y ago
You mean, why didn't he write a simple compression algorithm which actually shrunk the data? The short answer is, it was (almost certainly) impossible. You cannot compress random data. The only reason files you compress normally seem to compress is almost every file you come across normally contains some structure and therefore some redundancy.
- kunil 14y ago
  It is not random, input file is constant. Surely you can write an algorithm to compress a specific file.
  - ghshephard 14y ago
    But the sum of your decompression program and compressed file would then be larger than the original data file.
    - haberman 14y ago
      Mike's contest didn't limit the total size of the (input, random) data file, so you could make it arbitrarily large to make the cost of the decompression program arbitrarily small.
      - aes256 14y ago
        > [...] the contestant will send me a decompressor and a compressed file, which will together total in size less than the original data file, and which will be able to restore the compressed file to the original state.
      - ghshephard 14y ago
        If the data file is truly random, then there is no decompression program + compressed file that would be smaller than the original random file. That's the entire point.
        haberman 14y ago
        I'm not saying you could! I am only rebutting your earlier line of reasoning. IF you could write an algorithm that would compress a specific block of random data by any non-zero percentage, and IF you can make the original random data arbitrarily large, THEN the overall size of the code to implement this algorithm would not matter, because you could amortize it over an arbitrarily large random data file. However I am not claiming that such an algorithm to compress a specific block of random data exists! However other people are arguing that this is indeed theoretically possible: http://news.ycombinator.com/item?id=5025527 http://news.ycombinator.com/item?id=5025527
        cncool 14y ago
        What if the rng generates a file with massive redundancy by chance. Doesn't make it any less "truly random."
      - ozgung 14y ago
        Then how would you find redundancy in arbitrarily large random data?
        ars 14y ago
        See my comment http://news.ycombinator.com/item?id=5025527 http://news.ycombinator.com/item?id=5025527 This is a misunderstanding of the pigeonhole principle, which only applies to a specific compression algorithm. It does NOT apply if you get to write a custom algorithm for this data set. There are always redundancies in random data. If you can pick them out ahead of time with a custom algorithm it's certainly possible to "compress" it. Edit: I think I may be wrong here.

CJefferson 14y ago

This is an old story, but a fun one. To me it is clear that Mike Goldman should have paid up. Patrick clearly completed the challenge placed on him. While Patrick didn't obey the spirit of the challenge he obeyed the law, and Mike knew full well that the spirit of his challenge was impossible!

emn13 14y ago
Also, I'm not sure it was very wise of Mike to assume the data was truly incompressible. It's unlikely someone would manage to compress it (certainly for just 5k), but if you truly believe you have a source for billions or trillions of bits and that those bits then have exactly 100% as much entropy - well, you're taking a lot on faith. Indeed the fact that the content length was preselected implies some amount of regularity that might be (abused). Oh well.
emn13 14y ago
I don't agree - Patrick was (ab)using the discrepancy between file content size and file store size. For a single compressed file this may not be very relevant (hence its omission in the original problem description), but the changed rules proposed by patrick also didn't address it. As the designer of those new rules it was his responsibility to be clear, particularly since he was intending to use that discrepancy to his advantage. Yeah, Mike was stupid and not exactly nice - but that doesn't mean Patrick wasn't too.

vanni 14y ago

Previous discussion: http://news.ycombinator.com/item?id=4616704 http://news.ycombinator.com/item?id=4616704

Nate75Sanders 14y ago

Mike Goldman does not need to ever issue a challenge again. It is WIDELY agreed upon by people who engage in this activity regularly (known as "prop betting") that the spirit of the law does not matter one bit. He was way out of his element here and Patrick was well within his rights to do what he did.

dustyleary 14y ago
A great set of stories from an amazing life: http://www.amazon.com/Amarillo-Slim-World-Full-People/dp/B000GG4GS0 http://www.amazon.com/Amarillo-Slim-World-Full-People/dp/B00... Amarillo Slim engaged in these sort of prop bets all the time. Some of the more interesting stories where he "abuses the rules": * He bet that he could hit a golf ball a mile, "as long as bounces and rolls are allowed... flat ground of course"... When the wager was accepted, he teed off at a frozen pond, where it wasn't that difficult to accomplish. * Two variations on beating a champion at their own game: - Slim played Minnesota Fats at pool, "as long as I can provide the cue sticks"... And then beat Fats when they both had to play with broomsticks instead of real pool cues. - Slim bet that he could beat a very good ping pong player, "as long as I get to pick the rackets"... When the wager was accepted, Slim brought two identical cast iron skillets and let his opponent pick which "racket" he wanted. Without having practiced, his opponent didn't stand a chance. -- Later, someone else approached Slim and wanted to do the same bet. They had heard of the original bet, and had an Asian pingpong champion "ringer". (It seems pitifully obvious to me that Slim wouldn't pull the same trick after the story was out, but apparently this gambler had his Asian ringer practice with a skillet and thought he would be "safe")... For the second bet, Slim used "standard" Coca-Cola bottles, and won again.
SatvikBeri 14y ago
I love working with people like Patrick. In business, it's really easy to get caught up with assumptions, and come up with a design that does X, Y, and Z when all you really need is X. It's the people who're good at thinking outside the box and looking at the letter of the law, so to speak, who can take a step back and say "all we really need is X."

xentronium 14y ago

Why even bother with file concatenation? Just use 3M chars long filename for an empty file to "compress" 3Mb of data.

jlgreco 14y ago
DOS I assume.

ars 14y ago

The pigeonhole principle only applies to a specific compression algorithm. If you get to custom write the algorithm for the data you can arrange things so that for this datafile it will be smaller, yet larger for any other file, and still meet the principle. i.e. this is not actually impossible. If you can find ANY redundancy in the data, and you can code a very small decompresser specifically for that, you can probably win. And due to the nature of randomness, there are always numeric streaks, and other patterns in the data. The larger the datafile the better the chance of finding some sort of pattern or streak. The decompresser does not have to be large either - it would be perfectly legal to use a perl script for example. (i.e. so you don't have to use space writing IO handling code). Edit: I suspect I may be wrong here.

jgeralnik 14y ago
No. Let's say you have a file of size X. You want to write a program of size Y which will decompress an X-Y-1 sized file back to the original program. Does such a program and file exist for every file of size X? Using the pigeon hole principle, we can see that it does not. There are 2^X files of size X, but only 2^(X-1) inputs of length Y+X-Y-1. Therefore, not every file can be compressed this way. It doesn't matter what your decompressor is written in or how, you still can't do it.
- ars 14y ago
  I see your point.
- czr80 14y ago
  This is correct for the general case, but I think his argument is that for any specific file you can (almost certainly) find some redundancy and so find an algorithm to compress that specific file.
  - ars 14y ago
    That is exactly my argument. But now I think I'm wrong because what if you take the new data (i.e. the decompressor plus the compressed data), and try to compress that.

haberman 14y ago

Poetic justice. I love this quotation from Mike: "I think that I did not make a mistake except to believe that you truly intended to attempt to compress the data I was sending you." Mike is happily preying upon people by taking their money to enter what he believes is an impossible contest, but the moment he is outsmarted he appeals to morals and calls into question whether Patrick was acting honestly. I'm guessing there is some backstory on this newsgroup involving people who would claim to invent compression algorithms that do the impossible. I'm imagining that one day Mike thought "time to get these people to put their money where their mouth is." Still, it's pretty low to pose the challenge without saying "I'm taking this bet because it's highly unlikely that you can actually succeed. This is explained in the FAQ. Are you sure you want to give me $100?"

deleted 14y ago
[deleted]
jlgreco 14y ago
I am reminded of "apocalypse loans". (loans that only need to start being paid back, usually with incredibly steep interest, after an apocalypse that the borrower is anticipating. "If the world ends, you pay nothing!") I've seen such loans proposed often, but I don't know if anyone has ever actually taken one.
- ars 14y ago
  It exists: https://www.google.com/search?q=rapture+pet+care https://www.google.com/search?q=rapture+pet+care
svantana 14y ago
Actually, it is most likely possible, it's just very difficult. For example, it is likely that the data file was generated using a deterministic computer program. And that program is most likely a lot smaller than the outputted data. Therefore, one could use that very program as the "decompressor" - voila! The problem is - it would take astronomical computational resources to recreate that program, although there is a very straightforward algorithm to find it - just test out all possible programs starting from 0,1,2,3, and so on...

pavanky 14y ago

Makes me wonder if a "decompressor" adding generating hundreds of decompressed files by brute force (of which the original file is one) would be a valid solution. You could store a certain section of the original as the "compressed file"

algorias 14y ago

Even without doing any filesystem tricks, the challenge seems quite possible. While it's true that writing a compressor that compresses all input data is impossible, this barrier is removed because the compressor only needs to work on a single file.

praptak 14y ago
But the "decompressor" here is also more or less fixed - it's the environment in which the challenger program needs to run. So, the organizer of the challenge would need to be unlucky to pick a file that is compressible for this particular decompressor. Mathematically this has non-zero (albeit very small) probability but I'd wager that even having such file it would be unfeasible to find its compressed form. Maybe the file is the third million of bytes of pi squared, but how do you find this fact?
UnoriginalGuy 14y ago
But you're forgetting what the challenge actually is. It is file+decompressor < input. So by the very nature of it if your decompressor is non-zero in length, you have to find some efficiency/tricks to make the file smaller. Realistically the overhead on the decompressor will be 10 KB and that is before any kind of actual logic, so you are looking at shaving a minimum of 50 KB off of the original file (which is completely random).
- algorias 14y ago
  I'm not forgetting that. It's just that any specific random file will have (with high probability), patterns that can be exploited. It's not guaranteed to work on all files of course. The theoretical limit (per bijection argument) is that at most half the strings of length n can be losslessly represented in strings of length n-1, because there are half as many strings of length n-1 than of length n. So if, for example, 2% of files can actually be reduced in size (I don't know what the actual number is, and if it is even computable) that's still positive EV in a $100 vs $5000 bet.
  - jgeralnik 14y ago

splicer 14y ago

Just post the original data file on the web, then have your "decompression" program download the file. The "compressed" file could simply contain a URL.

splicer 14y ago

Here's another approach: Let the compressed file contain a hash (say, SHA1) of the original file. The decompression program then generates random files of the chosen size. If a generated file's hash doesn't match the desired hash, delete it. Now run the program for a very long time. The program is likely to eventually reproduce the original file (along with a bunch of files that happen to have the same hash), and you win :)

shubhamjain 14y ago
Would complete in perhaps just a couple of billions of years. :)
- UnoriginalGuy 14y ago
  But the rules didn't say the file had to be massive. You get to pick the size, so pick 100 Kb or similar. That would still take forever...
  - deleted 14y ago
    [deleted]
Beltiras 14y ago
Let's say you have a file of size n and a hash of size log(n). This means you have n/log(n) collisions (matches). I made a similar suggestion on another HN thread linking that same story (I suggested using two radically different hashing functions, one hash result would not necessarily have an evenly distributed result from the other hashing function when you vary the plaintext). Even while posting I thought that I must be wrong, I just didn't feel wrong about it. Now I do.
- splicer 14y ago
  The purpose of using a hash is just to avoid running out of disk space. With enough disk space, you don't even need to hash/delete files.
14y ago

deleted 14y ago

[deleted]

RyanZAG 14y ago

It is definitely possible to win this challenge though. Consider an arbitrary long series of integers. Somewhere within this series of integers, there will be some kind of randomly created pattern, since this is a property of an infinite set. eg. somewhere within the data set, there could be the values [1, 2, 3, ... 10] or [1, 3, 9, .. 27] or [1, 2, 4, 16, 32] - it does not matter which of these patterns, exist, only that there does exist some mathematical pattern in the data. The chances of there being no pattern in a big enough set of random data is impossible as there is a finite number of possible data combinations for bytes [1..256][1..256] etc. I guess a data set of 256^256 bytes would guarantee a pattern, but I'm sure there is a far smaller number that would give 99% confidence. Once you find a pattern in the data, you can remove that pattern and replace it with code that will recreate the pattern using a data offset. ie. you remove the pattern from the data completely, and replace it with a smaller piece of code to recreate that pattern exactly and insert it into the correct position. The key here is that once the data has been generated, it is no longer 'random data', but a fixed input. eg, you cannot compress a random unknown string of bytes, but you can compress the string [1,2,4,16..] The output data would have all possible mathematical patterns removed from it, and the decompression code would be just a list of mathematical functions and data offset points.

lifthrasiir 14y ago
You are recreating Kolmogorov complexity there. Kolmogorov complexity is defined as the minimal amount of program (for some programming language) to recreate the given string. By the definition, your strategy will compress the data no better than its Kolmogorov complexity. In this aspect, Kolmogorov complexity measures the data's true randomness. If the random data has been generated correctly its complexity should be near its length, however, so your strategy won't work. (And there is enough evidence that this was the case.) It does not matter whether the data is already known or not; it is the data's inherent randomness prohibiting you to compress it. To be sure, of course, Patrick Craig did not compress it in the pure information theoretic sense. Mike Goldman failed to equate the goal to that information theoretic compression however.
- RyanZAG 14y ago

DanBC 14y ago

If you're interested in efficient compression with English you might like the Hutter Prize (http://prize.hutter1.net/ http://prize.hutter1.net/) - a €50,000 prize if you can compress the 100MB file enwik8 to less than the current record of about 16MB. They claim it's an AI problem. I guess it could be if you're compressing a bunch of different English texts, but this challenge has a single text. A program that provides very efficient compression of this text might not be so great for other texts. Mike's challenge took a specially selected random file. As other people said, this was an attempt to show compression kooks that some files are not compressible (if you include the size of the decompressor).

kyle4211 14y ago

I can't find anything which solidly points to this challenge being 'likely' impossible. This all is not so simple as pointing at Kolmogorov complexity. Randomness is not so much inherent as relative to the machine on which you're running your program. http://rjlipton.wordpress.com/2011/06/02/how-powerful-are-random-strings/ http://rjlipton.wordpress.com/2011/06/02/how-powerful-are-ra...