3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ There is a related question I am interested in which I shared on the MathOverflow: mathoverflow.net/questions/350014/… $\endgroup$ Jan 8, 2020 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$ Jan 9, 2020 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$ Jan 9, 2020 at 8:46
  • 1
    $\begingroup$ Yes. I'd be interested to know the answer. $\endgroup$
    – Aryeh
    Jan 9, 2020 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$ Jan 9, 2020 at 9:41

Your Answer

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

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