Scaled dimension and nonuniform complexity

摘要

Resource-bounded dimension is a complexity-theoretic extension of classical Hausdorff dimension introduced by Lutz (in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169) 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(α2nn) has measure 0 in ESPACE for all 0⩽α⩽1, we now know that SIZE(α2nn) 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 zeroth-order dimension is precisely the dimension of Hausdorff (Math. Ann. 79 (1919) 157–179) 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 first-order dimension α in ESPACE.2.The classes SIZE(2nα),KTq(2nα), and KSq(2nα) have second-order dimension α in ESPACE.3.The classes KTq(2n(1−2−αn)) and KSq(2n(1−2−αn) have negative-first-order dimension α in ESPACE.