Treffer: CONDITIONAL DIMENSION IN METRIC SPACES: A NATURAL METRIC-SPACE COUNTERPART OF KOLMOGOROV-COMPLEXITY-BASED MUTUAL DIMENSION

It is known that dimension of a set in a metric space can be characterized in information-related terms -in particular, in terms of Kolmogorov complexity of different points from this set. The notion of Kolmogorov complexity $K(x)$ -the shortest length of a program that generates a sequence $x$ -can be naturally generalized to {\it conditional} Kolmogorov complexity $K(x:y)$ -the shortest length of a program that generates $x$ by using $y$ as an input. It is therefore reasonable to use conditional Kolmogorov complexity to formulate a conditional analogue of dimension. Such a generalization has indeed been proposed, under the name of {\it mutual dimension}. However, somewhat surprisingly, this notion was formulated in pure Kolmogorov-complexity terms, without any analysis of possible metric-space meaning. In this paper, we describe the corresponding metric-space notion of conditional dimension -a natural metric-space counterpart of the Kolmogorov-complexity-based mutual dimension.