?
Space-Bounded Online Kolmogorov Complexity is Additive
P. 133–142.
Bruno Bauwens, Marchenko M.
Abstract. The even online Kolmogorov complexity of a string x =
x1x2 · · · xn is the minimal length of a program that for all i ≤ n/2,
on input x1x3 · · · x2i−1 outputs x2i. The odd complexity is defined sim-
ilarly. 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 4/3 + O(log n). Let Cs (x) denote the Kolmogorov complexity with
space bound s. Here, we prove that the space-bounded dialogue com-
plexity with bound s + 6n + O (1) is at most Cs (x ) + O(log(sn)), where
n = |x|.