Abstract
In this paper we investigate effective versions of Hausdorff dimension which have been recently introduced by Lutz. We focus on dimension in the class E of sets computable in linear exponential time. We determine the dimension of various classes related to fundamental structural properties including different types of autoreducibility and immunity. By a new general invariance theorem for resource-bounded dimension we show that the class of p-m-complete sets for E has dimension 1 in E. Moreover, we show that there are p-m-lower spans in E of dimension Η(β) for any rational β between 0 and 1, where Η(β) is the binary entropy function. This leads to a new general completeness notion for E that properly extends Lutz's concept of weak completeness. Finally we characterize resource-bounded dimension in terms of martingales with restricted betting ratios and in terms of prediction functions.
Original language | English (US) |
---|---|
Pages (from-to) | 210-217 |
Number of pages | 8 |
Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |
State | Published - 2001 |
Event | 16th Annual IEEE Conference on Computational Complexity - Chicago, IL, United States Duration: Jun 18 2001 → Jun 21 2001 |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Computational Mathematics