×

Dimension is compression. (English) Zbl 1283.68175

Summary: Effective fractal dimension was defined by Lutz in 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.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
28A80 Fractals
28A78 Hausdorff and packing measures
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
37B05 Dynamical systems involving transformations and group actions with special properties (minimality, distality, proximality, expansivity, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, P., Mayordomo, E., Moser, P.: Bounded pushdown dimension vs Lempel Ziv information density. Technical Report TR07-051, ECCC: Electronic Coloquium on Computational Complexity (2007) · Zbl 1360.68453
[2] 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)
[3] Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. SIAM J. Comput. 37, 671–705 (2007) · Zbl 1144.68029
[4] Beigel, R., Fortnow, L., Stephan, F.: Infinitely-often autoreducible sets. In: Proceedings of the 14th Annual International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 2906, pp. 98–107. Springer, Berlin (2003) · Zbl 1205.68161
[5] Buhrman, H., Longpré, L.: Compressibility and resource bounded measure. SIAM J. Comput. 31(3), 876–886 (2002) · Zbl 1015.68082
[6] Cai, J., Hartmanis, J.: On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line. J. Comput. Syst. Sci. 49, 605–619 (1994) · Zbl 0824.68054
[7] Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (1991) · Zbl 0762.94001
[8] Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theor. Comput. Sci. 310, 1–33 (2004) · Zbl 1071.68027
[9] Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, Berlin (2010) · Zbl 1221.68005
[10] Hitchcock, J.M.: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theor. Comput. Sci. 289(1), 861–869 (2002) · Zbl 1061.68065
[11] Hitchcock, J.M.: Effective fractal dimension: foundations and applications. PhD thesis, Iowa State University (2003) · Zbl 1053.68053
[12] Hitchcock, J.M.: Fractal dimension and logarithmic loss unpredictability. Theor. Comput. Sci. 304(1–3), 431–441 (2003) · Zbl 1053.68053
[13] Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: The fractal geometry of complexity classes. SIGACT News 36, 24–38 (2005)
[14] 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) · Zbl 1103.68058
[15] Huffman, D.A.: Canonical forms for information-lossless finite-state logical machines. IRE Trans. Circuit Theory CT-6, 41–59 (1959). Also available in E.F. Moore (ed.), Sequential Machine: Selected Papers, pp. 866–871. Addison-Wesley (1964)
[16] Lempel, A., Ziv, J.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23, 337–343 (1977) · Zbl 0379.94010
[17] Lempel, A., Ziv, J.: Compression of individual sequences via variable rate coding. IEEE Trans. Inf. Theory 24, 530–536 (1978) · Zbl 0392.94004
[18] Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225–254. Springer, Berlin (1997) · Zbl 0880.68044
[19] Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32, 1236–1259 (2003) · Zbl 1026.68059
[20] Lutz, J.H.: The dimensions of individual strings and sequences. Inf. Comput. 187, 49–79 (2003) · Zbl 1090.68053
[21] Lutz, J.H.: Effective fractal dimensions. Math. Log. Q. 51, 62–72 (2005) · Zbl 1058.03044
[22] Mayordomo, E.: Contributions to the study of resource-bounded measure. PhD thesis, Universitat Politècnica de Catalunya (1994) · Zbl 0830.68071
[23] Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett. 84(1), 1–3 (2002) · Zbl 1045.68570
[24] Mayordomo, E.: Effective fractal dimension in algorithmic information theory. In: New Computational Paradigms: Changing Conceptions of What Is Computable, pp. 259–285. Springer, Berlin (2008) · Zbl 1144.68030
[25] Ryabko, B.Ya.: Coding of combinatorial sources and Hausdorff dimension. Sov. Math. Dokl. 30, 219–222 (1984) · Zbl 0581.94007
[26] Ryabko, B.Ya.: Noiseless coding of combinatorial sources. Probl. Inf. Transm. 22, 170–179 (1986) · Zbl 0613.94006
[27] Staiger, L.: Kolmogorov complexity and Hausdorff dimension. Inf. Comput. 103, 159–194 (1993) · Zbl 0789.68076
[28] Staiger, L.: A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory Comput. Syst. 31, 215–229 (1998) · Zbl 0896.68080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.