Let's suppose we encode two computable functions $f$ and $g$ as binary strings so $f,g \in \{0,1\}^*$. What I am curious about is whether we can find good upper and lower bounds for:

\begin{equation} K(f \circ g) \tag{1} \end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

My intuition suggests that we can compress each function separately and therefore:

\begin{equation} K(f \circ g) \leq K(f) + K(g) \tag{2} \end{equation}

and in general I think we can demonstrate that:

\begin{equation} K(f_n \circ f_{n-1} \circ ... \circ f_1) \leq \sum_{i=1}^n K(f_i) \tag{3} \end{equation}

However, my intuition also suggests that this is probably not the best upper bound and I am also curious about tight lower bounds.

Might there be a general theorem that gives the best possible upper and lower bounds?


Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.

Edit: You might need to pay additional bits for the composition, as for ordered pairings -- as observed by Emil Jeřábek in the comments.

  • $\begingroup$ There is a related question I am interested in which I shared on the MathOverflow: mathoverflow.net/questions/350014/… $\endgroup$ – Aidan Rocke Jan 8 '20 at 19:00
  • 1
    $\begingroup$ Wouldn't there be a logarithmic overhead to separate the descriptions of $f$ and $g$? Or is this prefix-free Kolmogorov complexity? $\endgroup$ – Emil Jeřábek Jan 9 '20 at 8:09
  • 1
    $\begingroup$ There are certainly examples where you need much less. For example, if $g$ is addition of a large constant, and $f$ is subtraction of the same constant, then $f\circ g$ is just the identity. The question is what is true for general $f$ and $g$, not for a particular example. $\endgroup$ – Emil Jeřábek Jan 9 '20 at 8:46
  • 1
    $\begingroup$ Yes. I'd be interested to know the answer. $\endgroup$ – Aryeh Jan 9 '20 at 9:29
  • 1
    $\begingroup$ Function composition should be no easier than ordered pairs. Given functions $f(x)$ and $g(x)$, let $f'$ and $g'$ be the functions $f'(x)=(f(x),x)$ and $g'((x,y))=(x,g(y))$. Then $K(f')=K(f)+O(1)$, $K(g')=K(g)+O(1)$, and $K((f,g))\le K(g'\circ f')+O(1)$. $\endgroup$ – Emil Jeřábek Jan 9 '20 at 9:41

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.