Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Dimension Is Compression

  • Conference paper
Mathematical Foundations of Computer Science 2005 (MFCS 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3618))

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ambos-Spies, K., Merkle, W., Reimann, J., Stephan, F.: Hausdorff dimension in exponential time. In: Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 210–217 (2001)

    Google Scholar 

  2. Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 632–643. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Beigel, R., Fortnow, L., Stephan, F.: Infinitely-often autoreducible sets. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 98–107. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  4. Buhrman, H., Longpré, L.: Compressibility and resource bounded measure. SIAM Journal on Computing 31(3), 876–886 (2002)

    Article  MATH  Google Scholar 

  5. Hitchcock, J.M.: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science 289(1), 861–869 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. Hitchcock, J.M.: Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University (2003)

    Google Scholar 

  7. Hitchcock, J.M.: Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science 304(1–3), 431–441 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Hitchcock, J.M., Vinodchandran, N.V.: Dimension, entropy rates, and compression. In: Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 174–183 (2004)

    Google Scholar 

  9. Kieffer, J.C.: En hui Yang. Grammar based codes: A new class of universal lossless source codes. IEEE Transactions on Information Theory 46, 737–754 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  10. Lempel, A., Ziv, J.: A universal algortihm for sequential data compression. IEEE Transaction on Information Theory 23, 337–343 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  11. Lempel, A., Ziv, J.: Compression of individual sequences via variable rate coding. IEEE Transaction on Information Theory 24, 530–536 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  12. Lutz, J.H.: Effective fractal dimensions. In: Mathematical Logic Quarterly. Preliminary version appeared in Computability and Complexity in Analysis, FernUniversität in Hagen, August 2003. Informatik Berichte, vol. 302, pp. 81–97 (2003) (to appear)

    Google Scholar 

  13. Lutz, J.H.: Dimension in complexity classes. SIAM Journal on Computing 32, 1236–1259 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  14. Lutz, J.H.: The dimensions of individual strings and sequences. Information and Computation 187, 49–79 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  15. Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters 84(1), 1–3 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  16. Mayordomo, E.: Effective Hausdorff dimension. In: Classical and New Paradigms of Computation and their Complexity Hierarchies, Papers of the conference, Foundations of the Formal Sciences III. Trends in Logic, vol. 23, pp. 171–186. Kluwer Academic Press, Dordrecht (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. de Informática e Ing. de Sistemas, Universidad de Zaragoza, María de Luna 1, 50018, Zaragoza, Spain

    María López-Valdés & Elvira Mayordomo

Authors
  1. María López-Valdés
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elvira Mayordomo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Mathematics, Gdansk University, Wita Stwosza 57, 80 952, Gdansk, Poland

    Joanna Jȩdrzejowicz  & Andrzej Szepietowski  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

López-Valdés, M., Mayordomo, E. (2005). Dimension Is Compression. In: Jȩdrzejowicz, J., Szepietowski, A. (eds) Mathematical Foundations of Computer Science 2005. MFCS 2005. Lecture Notes in Computer Science, vol 3618. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549345_58

Download citation

  • DOI: https://doi.org/10.1007/11549345_58

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-28702-5

  • Online ISBN: 978-3-540-31867-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation