CONDITIONAL DIMENSION IN METRIC SPACES: A NATURAL METRIC-SPACE COUNTERPART OF KOLMOGOROV-COMPLEXITY-BASED MUTUAL DIMENSION
Владик Крейнович, Luc Longpré, Olga M. Kosheleva · scholarworks - UTEP (The University of Texas at El Paso) · 2015
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 conditionalKolmogorov 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 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.