3
$\begingroup$

Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.

It is easy to see that almost all binary strings of length $N$ are incompressible by using the pigeonhole principle.

So my question is, how many strings of length $N$ are compressible?

In particular, let's assume that $K(S)$ is the Kolmogorov complexity of binary string $S$, which is of length $N$. Then I have the following three questions:

  1. Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N-1$?
  2. Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N/2$?
  3. Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq \log N$?

All of the above are for sufficiently large $N$.

$\endgroup$
4
$\begingroup$

A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$.

Conversely, considering the program $\Pi$ that gets an integer $r$ and a string $x$, and outputs $x$ together with $r$ many zeroes. Going over all strings of length $\ell$, this gives us $2^\ell$ many strings whose complexity is at most $\ell + O(\log N)$. Choosing $\ell = M - O(\log N)$, this shows that the number of strings of length $N$ such that $K(S) \leq M$ is at least $2^M/N^{O(1)}$.

This answers your first two questions up to a small multiplicative error. I suspect that the answer to the third one depends heavily on $N$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you for the answer - do you think the third one depends on $N$ beyond just if $N$ is large enough? $\endgroup$ – Mike Battaglia Nov 19 '19 at 20:19
  • 1
    $\begingroup$ It might depend on the Kolmogorov complexity of $N$. $\endgroup$ – Yuval Filmus Nov 19 '19 at 20:21

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.