Dimension in Complexity Classes

Top Cited Papers
Publisher Website
Google Scholar
Abstract
A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martin-gales. When the resource bound \math (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 \math yield internal dimension theories in E, E2, 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\math. Along with the elements of this theory, two preliminary applications are presented: 1. For every real number \math , the set FREQ(\math), consisting of all languages that asymptotically contain at most \math of all strings, has dimension H(\math) - the binary entropy of \math -in E and in E2. 2. For every real number \math, the set SIZE(\math), consisting of all languages decidable by Boolean circuits of at most \math gates, has dimension \math in ESPACE.

This publication has 8 references indexed in Scilit: