Dimension in Complexity Classes

A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound Δ (a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Hausdorff dimension (sometimes called "fractal dimension"). Other choices of the parameter Δ yield internal dimension theories in E, E 2 , 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 (X C) ∈ [0, 1]. Along with the elements of this theory, two preliminary applications are presented: For every real number 0 ≤ α ≤ 1 2, the set FREQ(≤ α), consisting of all languages that asymptotically contain at most α of all strings, has dimension H(α)---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.