Space-bounded online Kolmogorov complexity is additive

Abstract

The even online Kolmogorov complexity of a string $x=x_1{x}_2\cdots x_n$ is the minimal length of a program that for all $i\le n/2$, on input $x_1{x}_3\cdots x_{2i-1}$ outputs $x_{2i}$. The odd complexity is defined similarly. The sum of the odd and even complexities is called the dialogue complexity. In [Bauwens, 2014] it is proven that for all $n$, there exist $n$-bit $x$ for which the dialogue complexity exceeds the Kolmogorov complexity by $n\log \frac{4}{3}+O(\log n)$. Let ${\mathrm{C}}^s(x)$ denote the Kolmogorov complexity with space bound~$s$. Here, we prove that the space-bounded dialogue complexity with bound $s+6n+O(1)$ is at most ${\mathrm{C}}^s(x)+O(\log (sn))$, where $n=|x|$.

This update is just to add acknowledgements