4 ms·

But the challenge isn't to compress random strings, the challenge is to compress a specific random string. This means that given enough time, you should be able

• napillo 14y ago
  Exactly. Given enough time, you could come up with a compression algorithm that would generate the original file. It would only work for that one single file though.
• im3w1l 14y ago
  Yes it does. Lets say for simplicity that you are coding your solution in python, and that your output should be written to standard out, and the output file should be 10^6 bytes. Consider the function that takes a source file of at most 10^6 to the standard output of said program when interpreted. The set from which files you need to output, are drawn has cardinality 2^(10^6). The set of python programs (possibly invalid) that are strictly shorter has cardinality 2^(10^6-1). If all files were possible to compress, than a python interpreter would provide an injective map (one program gives maximum one output, possibly none if the program has errors) from a smaller set to a larger set. This is impossible. Therefore there is at least one file(actually a lot of them but this is beside the point) which cannot be compressed. Mike could send this one. EDIT: Messed up my bits and bytes and fenceposts: size 1: 256^(10^6). Size 2: sum (i=1 to 10^6) 256^(10^6-i)
  • praptak 14y ago
    > Mike could send this one. Only assuming he'd be able to generate one. Is there a known algorithm for generating a provably Kolmogorov-uncompressible strings?
    • Dylan16807 14y ago
      That's a tricky question. I'll start with a couple ground limitations. First off, you can't have an algorithm to make incompressible strings of an arbitrary length, because then you could tell it to make an string larger than your algorithm, aka larger than its own complexity. You also can't measure the complexity of arbitrary strings or you could loop over all possible strings and use it to build a generator. But if you use the rules of your execution environment you can make sufficiently small incompressible strings. For example, if we used python, "abc" can't be compressed. There just aren't any operations that we can use to shrink it. But "abcabc" could be written as "abc"*2 Any algorithm you use is going to have to depend highly on whatever environment you choose, and it won't be able to produce very long strings, so I don't know if anyone has really bothered. In comparison, it's really easy to use random numbers such that the chance of being able to remove n bits is 1/2^n. If you have even a few bytes of overhead, as shell scripting has, you're safe from luck.
  • im3w1l 14y ago
    Praptak: >Only assuming he'd be able to generate one. Is there a known algorithm for generating a provably Kolmogorov-uncompressible strings? In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion. In the practical case his odds are much better. Many potential programs will a) refuse to run and b) give the same output.
    • praptak 14y ago
      > In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion. An interesting result. Do you have a link to the proof?
      • Dylan16807 14y ago
        Proof: There are k strings of bytelength n. There are k * 256 strings of bytelength n+1. k input strings can decompress to at most k output strings Therefore only k / (k * 256) of length n+1 strings can be compressed by a byte. The reason for 'almost' is the miniscule number of strings that will compress more than one bye.
        • praptak 14y ago
          Ah right, I totally missed the fact that compression by 1 bit doesn't beat the challenge!
  • im3w1l 14y ago
    I really don't understand the mechanics of when a reply link appears. Anyway >An interesting result. Do you have a link to the proof? This is quite simple to understand. Just count how many files there are with size < n bytes (A), versus with size=n bytes (B). Size 1: sum (i=1 to n) 256^(n-i) ~= 256^(n-1). size 2: 256^(n). If you start pairing files from A up with files from B (equivalent to a compressing scheme), only 1/256 of files from B will be paired up. The remaining 255/256 of the files wont be paired up meaning they are not mapped to a smaller file, and cannot be compressed.
• dmfdmf 14y ago
  > But the challenge isn't to compress random strings, the challenge is to compress a specific random string. I agree and I think that this challenge is vulnerable albeit very difficult but not impossible, at least not via the pigeonhole principle. To be clear, the pigeonhole principle says for a given compression aglo and an input file of size n the output file must get bigger than n for some inputs of size n, i.e. it cannot compress all possible permutations of size n. However, the way the challenge is setup it is saying; given a specific random file of size n, find an algo that can compress the file so that the output plus decompressor is less than the input file. The pigeonhole principle does not say this is impossible. Granted, finding the algo that does this may mean solving P=NP or may take 10^32 lifetimes of the universe in calc time to find it but in principle it is not impossible. I admit, my understanding may be wrong and would really appreciate it if someone can explain to me my error here.