Asymmetry of the Kolmogorov complexity of online predicting odd and even bits

preprint2014arXivOpen access

Abstract

Symmetry of information states that C(x)+C(y∣x)=C(x,y)+O(log⁡C(x))C(x) + C(y|x) = C(x,y) + O(\log C(x)). We show that a similar relation for online Kolmogorov complexity does not hold. Let the even (online Kolmogorov) complexity of an n-bitstring x1x2...xnx_1x_2... x_n be the length of a shortest program that computes x2x_2 on input x1x_1, computes x4x_4 on input x1x2x3x_1x_2x_3, etc; and similar for odd complexity. We show that for all n there exist an n-bit x such that both odd and even complexity are almost as large as the Kolmogorov complexity of the whole string. Moreover, flipping odd and even bits to obtain a sequence x2x1x4x3…x_2x_1x_4x_3\ldots, decreases the sum of odd and even complexity to C(x)C(x).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.