Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-052 | 26th April 2001 00:00

Non-linear Inequalities between Predictive and Kolmogorov Complexity


Authors: Mikhail V. Vyugin, Vladimir Vyugin
Publication: 16th July 2001 18:21
Downloads: 1896


Predictive complexity is a generalization of Kolmogorov complexity
which gives a lower bound to ability of any algorithm to predict
elements of a sequence of outcomes. A variety of types of loss
functions makes it interesting to study relations between corresponding
predictive complexities.

Non-linear inequalities between predictive complexity of non-logarithmic
type and Kolmogorov complexity (which is close to predictive complexity
for logarithmic loss function) are the main subject of consideration
in this paper. We prove that asymptotically they differ on sequences
of length $n$ in the worst case by a factor equal to $\log n$. These estimates
cannot be improved. To obtain these inequalities we present estimates
of the cardinality of all sequences of given predictive complexity.

ISSN 1433-8092 | Imprint