Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-104 | 19th November 2004 00:00

Dimension is compression

RSS-Feed




TR04-104
Authors: Maria Lopez-Valdes, Mayordomo Elvira
Publication: 24th November 2004 18:49
Downloads: 3024
Keywords: 


Abstract:

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes.
Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous results for polynomial-time dimension haven't been found.

In this paper we remedy the situation by using the natural concept of reversible time-bounded compression for finite strings. We completely characterize polynomial-time dimension in terms of polynomial-time compressors.



ISSN 1433-8092 | Imprint