pith. sign in

arxiv: 0908.4457 · v1 · submitted 2009-08-31 · 💻 cs.IT · math.IT

Additivity of on-line decision complexity is violated by a linear term in the length of a binary string

classification 💻 cs.IT math.IT
keywords bitscomplexitydecisionbinarygivenlengthlinearon-line
0
0 comments X
read the original abstract

We show that there are infinitely many binary strings z, such that the sum of the on-line decision complexity of predicting the even bits of z given the previous uneven bits, and the decision complexity of predicting the uneven bits given the previous event bits, exceeds the Kolmogorov complexity of z by a linear term in the length of z.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.