3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Andrea Farruggia
    Jan 19, 2017 at 18:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jack G.
    Jan 19, 2017 at 22:16

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jack G.
    Jan 19, 2017 at 16:28
  • $\begingroup$ Suppose that the algorithm performs well on low-complexity input. Run it on any input. If it is a low-complexity input, it will compress it. If it is a high-complexity input, it cannot be compressed. So your algorithm would solve my undecidable problem. $\endgroup$
    – domotorp
    Jan 19, 2017 at 20:03
  • 1
    $\begingroup$ @domotorp: the algorithm might just perform poorly on the high-complexity input. The point is that you can't know if its output is a tight approximation of the Kolmogorov complexity or not. $\endgroup$
    – Andrea Farruggia
    Jan 19, 2017 at 20:30
  • 2
    $\begingroup$ $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. $\endgroup$
    – domotorp
    Jan 20, 2017 at 8:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Jan 23, 2017 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.