{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T13:10:05Z","timestamp":1737292205539,"version":"3.33.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T00:00:00Z","timestamp":1183507200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,12]]},"DOI":"10.1007\/s00224-007-9013-x","type":"journal-article","created":{"date-parts":[[2007,7,3]],"date-time":"2007-07-03T16:30:53Z","timestamp":1183480253000},"page":"471-497","source":"Crossref","is-referenced-by-count":0,"title":["Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets"],"prefix":"10.1007","volume":"43","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mar\u00eda","family":"L\u00f3pez-Vald\u00e9s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elvira","family":"Mayordomo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,4]]},"reference":[{"issue":"1","key":"9013_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"Ambos-Spies, K., Neis, H.-C., Terwijn, S.A.: Genericity and measure for exponential time. Theor. Comput. Sci. 168(1), 3\u201319 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9013_CR2","doi-asserted-by":"crossref","unstructured":"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\u2013217 (2001)","DOI":"10.1109\/CCC.2001.933888"},{"issue":"3","key":"9013_CR3","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1137\/S0097539703446912","volume":"37","author":"K.B. Athreya","year":"2007","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. SIAM J. Comput. 37(3), 671\u2013705 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9013_CR4","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1006\/jcss.1999.1650","volume":"59","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., van Melkebeek, D.: Hard sets are hard to find. J. Comput. Syst. Sci. 59(2), 327\u2013345 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9013_CR5","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1016\/S0022-0000(05)80073-X","volume":"49","author":"J. Cai","year":"1994","unstructured":"Cai, J., Hartmanis, J.: On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line. J. Comput. Syst. Sci. 49, 605\u2013619 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"9013_CR6","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G.J. Chaitin","year":"1975","unstructured":"Chaitin, G.J.: A theory of program size formally identical to information theory. J. Assoc. Comput. Mach. 22, 329\u2013340 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1\u20133","key":"9013_CR7","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.tcs.2006.02.022","volume":"359","author":"X. Gu","year":"2006","unstructured":"Gu, X.: A note on dimensions of polynomial size circuits. Theor. Comput. Sci. 359(1\u20133), 176\u2013187 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9013_CR8","unstructured":"Hitchcock, J.M.: Effective fractal dimension: foundations and applications. PhD thesis, Iowa State University (2003)"},{"issue":"1","key":"9013_CR9","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0020-0190(02)00454-4","volume":"86","author":"J.M. Hitchcock","year":"2003","unstructured":"Hitchcock, J.M.: Gales suffice for constructive dimension. Inf. Process. Lett. 86(1), 9\u201312 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9013_CR10","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/S0097539703426416","volume":"34","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M.: Small spans in scaled dimension. SIAM J. Comput. 34(1), 170\u2013194 (2004)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9013_CR11","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.tcs.2006.01.025","volume":"355","author":"J.M. Hitchcock","year":"2006","unstructured":"Hitchcock, J.M.: Hausdorff dimension and oracle constructions. Theor. Comput. Sci. 355(3), 382\u2013388 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9013_CR12","unstructured":"Hitchcock, J.M., Mayordomo, E.: Base invariance of feasible dimension. Manuscript (2003)"},{"key":"9013_CR13","first-page":"336","volume-title":"Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Pavan, A.: Hardness hypotheses, derandomization, and circuit complexity. In: Proceedings of the 24th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 336\u2013347. Springer, New York (2004)"},{"issue":"4","key":"9013_CR14","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1016\/j.jcss.2005.10.002","volume":"72","author":"J.M. Hitchcock","year":"2006","unstructured":"Hitchcock, J.M., Vinodchandran, N.V.: Dimension, entropy rates, and compression. J. Comput. Syst. Sci. 72(4), 760\u2013782 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9013_CR15","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.jcss.2003.09.001","volume":"69","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Scaled dimension and nonuniform complexity. J. Comput. Syst. Sci. 69, 97\u2013122 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9013_CR16","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/1086649.1086662","volume":"36","author":"J.M. Hitchcock","year":"2005","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: The fractal geometry of complexity classes. SIGACT News 36(3), 24\u201338 (2005)","journal-title":"SIGACT News"},{"key":"9013_CR17","unstructured":"Hitchcock, J.M., Pavan, A., Vinodchandran, N.V.: Partial bi-immunity, scaled dimension, and NP-completeness. Theory Comput. Syst., doi: 10.10007\/s00224-007-9000-2"},{"issue":"2","key":"9013_CR18","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D.W. Juedes","year":"1995","unstructured":"Juedes, D.W., Lutz, J.H.: The complexity and distribution of hard problems. SIAM J. Comput. 24(2), 279\u2013295 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9013_CR19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1006\/inco.1996.0017","volume":"125","author":"D.W. Juedes","year":"1996","unstructured":"Juedes, D.W., Lutz, J.H.: Completeness and weak completeness under polynomial-size circuits. Inf. Comput. 125(1), 13\u201331 (1996)","journal-title":"Inf. Comput."},{"key":"9013_CR20","first-page":"1413","volume":"14","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: On the notion of a random sequence. Sov. Math. Dokl. 14, 1413\u20131416 (1973)","journal-title":"Sov. Math. Dokl."},{"key":"9013_CR21","first-page":"206","volume":"10","author":"L.A. Levin","year":"1974","unstructured":"Levin, L.A.: Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Probl. Inf. Transm. 10, 206\u2013210 (1974)","journal-title":"Probl. Inf. Transm."},{"key":"9013_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Berlin (1997)","edition":"2"},{"key":"9013_CR23","unstructured":"Lindner, W.: On the polynomial time bounded measure of one-truth-table degrees and p-selectivity. Diplomarbeit, Technische Universit\u00e4t Berlin (1993)"},{"key":"9013_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1007\/11549345_58","volume-title":"Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science","author":"M. L\u00f3pez-Vald\u00e9s","year":"2005","unstructured":"L\u00f3pez-Vald\u00e9s, M., Mayordomo, E.: Dimension is compression. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 3618, pp. 676\u2013685. Springer, New York (2005)"},{"key":"9013_CR25","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32, 1236\u20131259 (2003)","journal-title":"SIAM J. Comput."},{"key":"9013_CR26","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0890-5401(03)00187-1","volume":"187","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: The dimensions of individual strings and sequences. Inf. Comput. 187, 49\u201379 (2003)","journal-title":"Inf. Comput."},{"issue":"1","key":"9013_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0190(02)00343-5","volume":"84","author":"E. Mayordomo","year":"2002","unstructured":"Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Inf. Process. Lett. 84(1), 1\u20133 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9013_CR28","first-page":"219","volume":"30","author":"Ya.B. Ryabko","year":"1984","unstructured":"Ryabko, Ya.B.: Coding of combinatorial sources and Hausdorff dimension. Sov. Math. Dokl. 30, 219\u2013222 (1984)","journal-title":"Sov. Math. Dokl."},{"key":"9013_CR29","first-page":"170","volume":"22","author":"Ya.B. Ryabko","year":"1986","unstructured":"Ryabko, Ya.B.: Noiseless coding of combinatorial sources. Probl. Inf. Transm. 22, 170\u2013179 (1986)","journal-title":"Probl. Inf. Transm."},{"key":"9013_CR30","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1006\/inco.1993.1017","volume":"102","author":"L. Staiger","year":"1993","unstructured":"Staiger, L.: Kolmogorov complexity and Hausdorff dimension. Inf. Comput. 102, 159\u2013194 (1993)","journal-title":"Inf. Comput."},{"key":"9013_CR31","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s002240000086","volume":"31","author":"L. Staiger","year":"1998","unstructured":"Staiger, L.: A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory Comput. Syst. 31, 215\u2013229 (1998)","journal-title":"Theory Comput. Syst."},{"key":"9013_CR32","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","volume":"25","author":"A.K. Zvonkin","year":"1970","unstructured":"Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25, 83\u2013124 (1970)","journal-title":"Russ. Math. Surv."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9013-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9013-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9013-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T04:06:24Z","timestamp":1737173184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9013-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,4]]},"references-count":32,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9013"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9013-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2007,7,4]]}}}