Space-Bounded Online Kolmogorov Complexity is Additive
摘要
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_1x_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 [4] 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 \({{\,\textrm{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 \({{\,\textrm{C}\,}}^{s}(x) + O(\log (sn))\) , where \(n=|x|\) .