Dimension in complexity classes

A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martin-gales. When the resource bound Δ(a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Haludolff dimension (sometimes called “fractal dimension”). Other choices of the parameter Δ yield internal dimension theories in E, E₂, ESPACE, and other complexity classes, and in the class of all decidable problems. In general, if C is such a class, then every set X of languages has a dimension in C, which is a real number dim(X|C)∈[0, 1]. Along with the elements of this theory two preliminary applications are presented: 1. For every real number 0⩽α⩽½, the set FREQ(≈α), consisting of all languages that asymptotically contain at most α of all strings, has dimension ℋ(α)-the binary entropy of α-in E and in E₂. 2. For every real number 0⩽α⩽1, the set SIZE(α2ⁿ/n), consisting of all languages decidable by Boolean circuits of at most α2ⁿ/n gates, has dimension α in ESPACE