Scaled Dimension and Nonuniform Complexity

John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo

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(α2n / n) has measure 0 in ESPACE for all 0 ≤ α ≤ 1, we now know that SIZE(α2n / 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 ith-order dimension of X in suitable complexity classes. The 0th-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) ≥ n2.

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

Journal Version:

Preliminary Version: