# Compression algorithms for low-complexity strings?

Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there compression algorithms that, when restricted to input $s$ where $n_s / n_s^*$ is large, achieve provably tighter approximations than algorithms with unrestricted input?

In other words, can a compression algorithm specifically tailored for low complexity inputs outperform the best general input algorithm on inputs of low complexity?

Admittedly, the question isn't completely precise, but I'm hoping to find results of roughly the same flavor.

Edit: See domotorp's answer below for a proof of the impossibility of a large class of low-complexity compression algorithms under the TM model. Note that this result does not bar the possibility of compression algorithms where the function $A$ (see the answer for context) is non-computable. For example, setting $A(|x|) = 100*BB^{-1}(|x|)$ where $BB^{-1}$ is the inverse busy beaver function, could make for a useful compression algorithm and is not covered by the proof.

• I expect the answer to be "no", because any such algorithm should be able to synthesize Turing Machines from arbitrary strings (think e.g. about a TM machine that produces an infinite string of data using a pseudorandom generator. Since the TM has $O(1)$ size and the text is unbounded, any reasonable "provably tight approximation" should involve a $O(1)$ output). Jan 19, 2017 at 18:04
• I agree with your hunch, but notice what I'm looking for is weaker than a provably tight approximation: I'm only looking for an improvement over the best general input algorithm. For the case of Turing Machines, the worst case is achieved with pseudorandom strings where $n^*$ is $O(1)$ but the size of the compressed string is $O(n)$. An algorithm that returns a TM of size, say, $O(\sqrt{n})$ when given strings where $n^*$ is $O(1)$ would provide a tighter approximation than the best general input algorithm. Jan 19, 2017 at 22:16

No, at least not in the TM model, i.e., for Kolmogorov complexity. Given $g(x) \leq f(x) \leq |x|$ for all $x$ where $g$ is monotonic and unbounded and $f$ is recursive, it is not possible to enumerate an infinite subset of $\{ x : K(x) > f(x)\}$.
Suppose for the sake of contradiction there exists a recursive function $h$, the low-complexity compression algorithm, which on input $x$ outputs a TM that reproduces $x$ and has the following additional property: Let $A:\mathbb{N} \rightarrow \mathbb{N}$ and $B:\mathbb{N} \rightarrow \mathbb{N}$ be given such that both are recursive, $A(|x|) \leq B(|x|) \leq |x|$ for all $x$, and $A$ is unbounded. Then $\forall x, K(x) \leq A(|x|) \implies |h(x)| \leq B(|x|)$.
Now choose $f(x) = A(|x|)$. We wish to enumerate an infinite subset of $\{x: K(x) > A(|x|)\}$. Note that there are infinite $x$ such that $K(x) > B(|x|)$ because $B(|x|) \leq |x|$. For any such $x$, $|h(x)| \geq K(x)$ by the definition of $K$ so $|h(x)| > B(|x|)$. Then for a generic string $x$, $|h(x)| > B(|x|) \implies K(x) > A(|x|)$ and we can enumerate an infinite subset of $\{x: K(x) > A(|x|)\}$, a contradiction.
• Yes, finding or approximating $n^*$ is undecidable in the TM model, but it's not obvious to me that this would exclude the possibility of an algorithm that performs well on low complexity inputs without "knowing" whether each input is in fact low-complexity. Jan 19, 2017 at 16:28
• $K(x)=O(1)$ for only finitely many strings, so it doesn't make much sense to study this problem. If, however, you replace $O(1)$ with any function $f$ that tends to $\infty$, as I wrote in my answer, then you get an undecidable problem that is much weaker than what you wrote in the last line of your last comment. Jan 20, 2017 at 8:04
• I don't understand why this wouldn't work. If $K(x)>|x|^{0.2}$, then $|g(x)|>|x|^{0.2}$. If $|g(x)|>|x|^{0.2}$, then $K(x)>|x|^{0.1}$. Therefore for the obvious choice of $f(x)=|x|^{0.1}$ we get a contradiction. Jan 23, 2017 at 8:19