4 ms·

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.
            • jessaustin 14y ago
              ...except in this case a complex custom algorithm will make the decompressor bigger which will count against your total size.
            • CJefferson 14y ago
              Except, that 'specific compression algorithm' could be "attach an x86 program to your compressed data, which I will run", which then covers all algorithms you might care to submit.
        • yk 14y ago
          It is not possible, without some amount of luck. The reason is, that you can think of the data + decompressor as a program which contains the data as some binary blob. There are less than 2^s different possible executables, where s is the filesize of the compressor together with the compressed data. And therefore 2^s different outputs. On the other hand, there are 2^l different original files (l is the filesize). Therefore only a few files can be compressed to a smaller file size. To be precise, you can compress at best 2^s files out of the 2^l ones by l-s bits. Thinking a bit further, for a file of length l, the probability getting a file that can be compressed is smaller than \sum_{k=1}^{l-1} 2^{-k} [1] which approaches 1 for l against infinity. ( So just based on the upper limit, your odds seem to get better for longer programs. :) [1]rendered formula for the equation (hope this works): http://latex.codecogs.com/gif.latex?\sum_{k=0}^{l-1}%202^{-k} http://latex.codecogs.com/gif.latex?\sum_{k=0}^{l-1}%202^{-k...