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

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?

• 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. – D.W. Jan 17 '17 at 0:43