Kolmogorov Complexity and Compression Schemes

Question

My question concerns strings with low Kolmogorov Complexities and if there is a single compression scheme that can be used to compress them

I have been introduced to Kolmogorov Complexity through Introduction to Theory of Computation, According to Sipser, the minimal description of a string $x$, written $d(x)$ is the shortest string $\langle M,w \rangle$ such that when a TM $M$ is run with $w$ as its input it halts with $x$ on its tape, if so we say that the Descriptive (Kolmogorov) complexity of the string $K(x) = |d(x)|$ $

Now for any string $x$ with logarithmic descriptive complexity, so $K(x) = \mathcal{O}(\log n)$, is there a lossless compression scheme (like Run-length encoding ) which is guaranteed to compress $x$ up to a $\log$ factor (I am not trying to compute the K-complexity, rather assume we are given a set of all strings for which $K(x) = \mathcal{O}(\log n)$, is there a single algorithm that can compress all of them?)

So for example, if we have the string $\overbrace{01010101 \ldots}^{\text{01 repeated N times}}$ we may compress it in a manner similar to Run-length encoding as $(01)_{\times N}$ which I use to denote $01$ repeated $N$ times (I use this notation since it comes handy later but we may write it just as N 01 ignoring delimiters for now), the compressed string $w$ has about $\log N$ size

My intuition is that strings with such low descriptive complexity have regularities that can be exploited by some algorithm, I may reform my question into asking if strings with $K(x) = \mathcal{O}(\log n)$ share some form of redundancy/regularity that can be exploited by some algorithm to produce a small compressed string (for example if such strings always include runs of repeated strings like $010101 \ldots$)

So the setting is as follows, given any string $x$, $|x| = N = 2^n$, fow which $K(x) = \mathcal{O}(\log N)$ we wish to have an algorithm (a single algorithm for all those strings) that can compress $x$ into a string $w$, where $|w| = poly(n)$, such that some TM $M'$ when run on $w$ halts with $x$ on its tape

I am looking for am algorithm that informs me of the structure of the compressed string, in other words it guarantees that the compressed string appears in some fixed format. I believe the way to approach this is thinking about a single algorithm that exploits some shared regularity/redundancy about those strings, I understand that a Universal TM $U$ can be fed $M,w$ as $x$'s description, but that's a possibly different $M$ (decompression algorithm) for each string (and hence a possibly different format/structure for the compressed string), I am asking if a single $M$ exists such that for every string $x$ where $|x| = N = 2^n$, a string $w, |w| = poly(n) $ exists such that $M(w) = x$, so basically my question concerns redundancies and regularities (as far as my intuition can tell) in such strings and an algorithm to exploit them rather than a smart way to use $M,w$ (so we might think as if someone tells us that $K(x) = \mathcal{O}(\log N)$ without telling us about $M,w$, also see my attempt below for an example of what I am trying to prove)

---

Finally here is my modest attempt, I am new to descriptive complexity so feel free to guide me. After some reading, it seems lots of proofs concerning Kolmogorov complexity revolve around randomness. If a string's Kolmogorov complexity is the same size as the original string's size we can say that the string is random. Since our string $x$ has a low complexity $K(x) = \mathcal{O}(\log n)$ (pardon me for switching between $n$ and $N$ but you get the idea) then it cannot be random. My attempt is to provide a compression scheme and argue that if the string cannot be compressed within this scheme then it shows some level of randomness which is unallowable due to the low descriptive complexity. The type of redundancy/regularity I wish to exploit is runs of repeated data.

First, I would present the decompression algorithm using an example, consider the string $$\overbrace{01 \ 01 \ 011 \ 011 \ 011 \ 01 \ 01 \ 011 \ 011 \ 011 \ldots}^{01 \ 01 \ 011 \ 011 \ 011 \text{ repeated N times}}$$

I would compress this string as $$((01)_{\times 2}(011)_{\times 3})_{\times N}$$ so basically its a small modification on the Run-length encoding

Now, if we consider each of the sequences in this string (like $01 \text{ and } 011$), our goal would be to show that their are polynomially many sequences each of which is polynomially long, if so then the entire compressed string is of polynomial size which is our goal (so if $N = 2^n$, and the number of sequences appearing in compressed string is $poly(n)$ and their sizes are also $poly(n)$ then the total is a $poly(n)$ size compressed string)

It gets challenging starting here, I would argue that if one of the sequences is not of polynomial length (for example of exponential length), and it couldn't be compressed any further then that implies randomness (since now we have an exponentially long random string) which is unallowed (due to low descriptive complexity), in a similar manner if we have exponentially many sequences, which cannot be grouped together to be compressed further, then I would assign each of those sequences a character from some alphabet (so every sequence $01$ would be replaced by $a$ for example) and argue that the resulting string is exponentially long yet random and cannot be compressed, again which is unallowed

So to stress the idea, if we use the $M,w$ from $x$'s description to generate $x$, then we use the compression algorithm $M'$ (which does the compression algorithm above), and the result ends producing up some exponentially long incompressible random string, then $\hat M,w,$ (where $\hat M$ mimics $M$ then $M'$) would serve as a short description for that string, which is a contradiction

I understand there might be a leap in my logic, specially concerning that $M'$ may produce an exponentially long non-random string which is simply long because $M'$ could not compress it and not because it is random, any guidance on proof techniques or resources would be highly appreciated, also any resources talking about compression down to logarithmic factor would be great even if it uses some other methods (like Entropy), my main goal is to be aware of the structure of the compressed string

Answer 1

I think this is a very difficult problem. To put it in context, the basic reference on Kolmogorov complexity is the book by Li and Vitanyi.

Recently, Vitanyi published a review article in the journal Entropy on methods of approximating Kolmogorov complexity.

Recently there have been several proposals regarding how to compute or approximate in some fashion the Kolmogorov complexity function. There is a proposal that is popular as a reference in papers that do not care about theoretical niceties, and a couple of proposals that do make sense but are not readily applicable. Therefore, it is timely to survey the field and show what is and what is not proven.

The Kolmogorov complexity $C(x)$ is incomputable in a strong sense. In fact (Theorem 1 in the survey) one cannot cheat on partial sets [such as sets of primes as a subset of all naturals]:

no partial computable function defined on an infinite set of points can coincide with C(x) over the whole of its domain of definition.

Some problems with proposed approximations are also discussed there:

Let us assume that the computer used in the experiments fills the rôle of the required optimal Universal Turing machine for the desired Kolmogorov complexity, the target string, and the universal distribution involved. However, the $O(1)$ term in the Coding theorem is mentioned but otherwise ignored in the experiments and conclusions about the value of the Kolmogorov complexity as reported in [17,18]. Yet the experiments only concern small values of the Kolmogorov complexity, say smaller than 20, so they are likely swamped by the constant hidden in the O(1) term.

The article is available here.

One last comment, it is an open problem whether a prime can be computed in an efficient way. The following paper which was the outcome of the collaborative Polymath project run by Terence Tao has some results:

Abstract. Given a large positive integer $N,$ how quickly can one construct a prime number larger than $N$ (or between $N$ and $2N$)? Using probabilistic methods, one can obtain a prime number in time at most $\log^{O(1)} N$ with high probability by selecting numbers between $N$ and $2N$ at random and testing each one in turn for primality until a prime is discovered. However, if one seeks a deterministic method, then the problem is much more difficult, unless one assumes some unproven conjectures in number theory.

So even computing some prime in $(N,2N]$ is difficult.