I have two bitstrings that are 100 bits long. Bitstring A has a Kolmogorov complexity (KC) of 90 and bitstring B has a KC of 10. Intuitively, I think bitstring B is probably easier to compress than bitstring A.

"Easier to compress" means a larger proportion of 100 bit bitstrings with B's KC can be compressed by a standard compression algorithm, than bitstrings with A's KC.

What I mean is that B probably has much more regularity that can be exploited by a compression algorithm such as Lempel-Ziv, whereas A is probably much more random and irregular.

Is this intuition correct? If so, how is this relation quantified? Can I say B is 9 times as likely to be compressible than A?

  • 1
    $\begingroup$ Can you define what you mean by "easier"? I don't think the question is well-defined. In particular, I don't think there's any formal, well-defined notion of "easier to compress". You can certainly say that B's compression ratio is 9 times as high as A's compression ratio. $\endgroup$
    – D.W.
    Jan 17 '17 at 0:43

I think your intuition is not correct. We can't effectively reason over the space of all programs, even all programs up to a given size (e.g. 90 for A and 10 for b) and it's not certain what the units are in your given KC measures for B and A.

As a simple example, imagine a program B that decompressed a highly compressible message and then encrypted it using some cipher and a hardcoded key. And imagine a different program A that simply output a hardcoded random string of the same length as the one produced in B. Given a long enough output, you could make K(output(B)) << K(output(A)), but both would be highly uncompressible without having the decryption key for B available.

What you're talking about sounds something like this: https://en.wikipedia.org/wiki/Algorithmic_probability. It is uncomputable, but if you are willing to e.g. limit the execution time of programs and randomly sample from random programs, you can start to analyze very simple examples.

  • $\begingroup$ This is a good exceptional case, but is it a typical case? While particular bitstrings with low KC may be very difficult to find a decompressor, is this the case with most bitstrings of low KC? $\endgroup$
    – yters
    Feb 8 '17 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.