Abstract:
Resource-bounded dimension is a complexity-theoretic extension of classical Hausdorff dimension introduced by Lutz (2000) in order to investigate the fractal structure of sets that have resource-bounded measure 0. For example, while it has long been known that the Boolean circuit-size complexity class SIZE(α2ⁿ / n) has measure 0 in ESPACE for all 0 ≤ α ≤ 1, we now know that SIZE(α2ⁿ / n) has dimension α in ESPACE for all 0 ≤ α ≤ 1.

The present paper furthers this program by developing a natural hierarchy of "rescaled" resource-bounded dimensions. For each integer i and each set X of decision problems, we define the i^th-order dimension of X in suitable complexity classes. The 0^th-order dimension is precisely the dimension of Hausdorff (1919) and Lutz (2000). Higher and lower orders are useful for various sets X. For example, we prove the following for 0≤ α ≤ 1 and any polynomial q(n) ≥ n².

1. The class SIZE(2^αn) and the time- and space-bounded Kolmogorov complexity classes KT^q(2^αn) and KS^q(2^αn) have 1^st-order dimension α in ESPACE.
2. The classes SIZE(2^nα), KT^q(2^nα), and KS^q(2^nα), and have 2^nd-order dimension α in ESPACE.
3. The classes KT^q(2ⁿ(1-2^-αn)) and KS^q(2ⁿ(1-2^-αn))have -1^st-order dimension α in ESPACE.

Journal Version:

• Journal of Computer and System Sciences, 69(2):97-122, 2004.
  [PostScript | PDF | DOI link]

Preliminary Version:

• Proceedings of the 30th International Colloquium on Automata, Languages, and Programming (Eindhoven, The Netherlands, June 30-July 4, 2003), Lecture Notes in Computer Science 2719, pages 278-290. Springer-Verlag, 2003.
  [Publisher's Page]