**Abstract**:

This paper develops relationships between resource-bounded dimension,
entropy rates, and compression. New tools for calculating dimensions
are given and used to improve previous results about circuit-size
complexity classes.

Approximate counting of SpanP functions is used to prove that the
NP-entropy rate is an upper bound for dimension in
Δ^{E}_{3}, the third level of the
exponential-time hierarchy. This general result is applied to
simultaneously improve the results of Mayordomo
(1994) on the measure on P/poly in Δ^{E}_{3}
and of Lutz
(2000) on the dimension of exponential-size circuit complexity
classes in ESPACE.

Entropy rates of efficiently rankable sets, sets that are optimally compressible, are studied in conjunction with time-bounded dimension. It is shown that rankable entropy rates give upper bounds for time-bounded dimensions. We use this to improve results of Lutz (1992) about polynomial-size circuit complexity classes from resource-bounded measure to dimension.

Exact characterizations of the effective dimensions in terms of Kolmogorov complexity rates at the polynomial-space and higher levels have been established, but in the time-bounded setting no such equivalence is known. We introduce the concept of polynomial-time superranking as an extension of ranking. We show that superranking provides an equivalent definition of polynomial-time dimension. From this superranking characterization we show that polynomial-time Kolmogorov complexity rates give a lower bound on polynomial-time dimension.

*Journal of Computer and System Sciences*, 72(4):760-782, 2006.

[PostScript | PDF | DOI link]*Proceedings of the*(Amherst, Massachusetts, June 21-24, 2004), pages 174-183. IEEE Computer Society Press, 2004.*19th IEEE Conference on Computational Complexity*

[DOI link]