Is a bitstring easier to compress if it has lower Kolmogorov complexity?

Question

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?

Answer 1

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.