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} / n)
has measure 0 in ESPACE for all
0 ≤ α ≤ 1, we now know that
SIZE(α2^{n} / 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^{2}.
Journal Version:
Preliminary Version: