5
$\begingroup$

Given a natural number $n$ denote by $K(n)$ its Kolmogorov complexity.

Let $m, n$ be two natural numbers. The relative Kolmogorov complexity $K_m(n)$ of $n$ with respect to $m$ is the minimum length of a program that takes $m$ as input and outputs $n$.

Question: can the ratio of $K(m)+K_m(n)$ to $K(n)+K_n(m)$ be arbitrarily close to 2?

$\endgroup$
3
  • 2
    $\begingroup$ By symmetry of information, $K(\langle m,n \rangle) = K(n) + K_n(m) + \Theta(\log(\max(|m|,|n|)))$ (where $|m|$ is the length of the binary representation of $m$). I feel like that means the answer is no. $\endgroup$
    – Ville Salo
    Commented Sep 2, 2021 at 10:20
  • $\begingroup$ Of course the result does not directly follow from that formula, $m, n$ could be long but have very low complexity. In any case suggest looking at the proof of SoI to see if it is helpful, if you did not do that already. E.g. people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf seems pretty understandable. $\endgroup$
    – Ville Salo
    Commented Sep 2, 2021 at 11:03
  • $\begingroup$ @VilleSalo Perhaps you could make this an answer? $\endgroup$ Commented Jun 18, 2022 at 6:56

2 Answers 2

1
$\begingroup$

The answer is "yes", but the question (and answer) is not very interesting. Recall that Kolmogorov complexity is defined relative to some arbitrary "reference" Universal Turing Machine (UTM). We can always choose the reference UTM $U$ such that $$\frac{K_U(m)+K_U(n\vert m)}{K_U(n)+K_U(m|n)}=2\tag{1}$$ for some particular $m$ and $n$ (we've used slightly more standard notation above for convenience).

In general, it is only when dealing with complex strings (i.e., those with large $K_U(x)$) that the dependence on the reference UTM $U$ becomes negligible, and Kolmogorov complexity becomes an interesting mathematical object.

Let us show that $(1)$ holds for some reference UTM, using binary encoding (rather than natural numbers) to make things more explicit. Consider a UTM which maps $U(\texttt{0})=\texttt{10}$ and $U(\texttt{10})=0$ (we assume that $U$ can also take $\texttt{11}+$[some prefix-free arbitrary program], so that it is universal). Then take $m=\texttt{0}$ and $n=\texttt{10}$ in $(1)$, giving $$\frac{K_U(\texttt{0})+K_U(\texttt{10}|{\texttt{0}})}{K_U(\texttt{10})+K_U(\texttt{0}|{\texttt{10}})}=\frac{K_U(\texttt{0})}{K_U(\texttt{10})}=\frac{\ell(\texttt{10})}{\ell(\texttt{0})}=2.$$

$\endgroup$
1
$\begingroup$

Under some natural assumptions on $m, n$ (called $x, y$ below), the answer is "no".

Let me work with binary words instead of numbers, and $|x|$ denotes the length of a word $x$. Specifically the answer to the question is "no" when we consider only words which are sufficiently complicated, more precisely, words which take essentially more bits to describe than their length. In this case the ratio of the quantities is about $1$.

This follows from Symmetry of Information [1], one version of which is the formula $$ K(x) + K_x(y) = K(\langle x, y \rangle) \pm O(\log (\max(|x|, |y|))). $$

Here, $\langle x, y \rangle$ is some natural pairing function, and you can read $O(\log (\max(|x|, |y|)))$ as the upper bound on how many bits you need to describe lengths of the words $x, y$. Note that the quantity on the right is symmetric in $x, y$.

Writing $k = K(\langle x, y \rangle)$ and $\epsilon = O(\log ( \max(|x|, |y|)))$, we get $$ \frac{K(x) + K_x(y)}{K(y) + K_y(x)} = \frac{k \pm \epsilon}{k \pm \epsilon} \approx 1 $$ when $\epsilon = o(k)$, i.e. when describing the words takes many times more bits than just describing their lengths.

[1] Fortnow, Lance, Kolmogorov complexity, Downey, Rod (ed.) et al., Aspects of complexity. Minicourses in algorithmics, complexity and computational algebra. Mathematics workshop, Kaikoura, New Zealand, January 7-15, 2000. Berlin: de Gruyter. de Gruyter Ser. Log. Appl. 4, 73-86 (2001). ZBL1027.68610.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .