Abstract:
Effective fractal dimensions were introduced by Lutz (2003) in order
to study the dimensions of individual sequences and quantitatively
analyze the structure of complexity classes. Interesting connections
of effective dimensions with information theory were also found,
implying that constructive dimension as well as polynomial-space
dimension are invariant under base-change while finite-state dimension
is not.
We consider the intermediate case, polynomial-time dimension, and prove that it is indeed invariant under base-change by a nontrivial argument which is quite different from the Kolmogorov complexity ones used in the other cases.
Polynomial-time dimension can be characterized in terms of prediction-loss-rate, entropy, and compression algorithms. Our result implies that in an asymptotic way each of these concepts is invariant under base-change.
A corollary of the main theorem is any polynomial-time dimension 1 number (which may be established in any base) is an absolutely normal number, providing an interesting source of absolute normality.
Versions: