Computer Science – Computational Complexity
Scientific paper
2002-03-12
Computer Science
Computational Complexity
24 pages
Scientific paper
A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound \Delta (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 \Delta 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(X|C) in [0,1]. Along with the elements of this theory, two preliminary applications are presented: 1. For every real number \alpha in (0,1/2), the set FREQ(<=\alpha), consisting of all languages that asymptotically contain at most \alpha of all strings, has dimension H(\alpha) -- the binary entropy of \alpha -- in E and in E2. 2. For every real number \alpha in (0,1), the set SIZE(\alpha* (2^n)/n), consisting of all languages decidable by Boolean circuits of at most \alpha*(2^n)/n gates, has dimension \alpha in ESPACE.
No associations
LandOfFree
Dimension in Complexity Classes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dimension in Complexity Classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dimension in Complexity Classes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-252325