{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:25:59Z","timestamp":1778732759381,"version":"3.51.4"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,5,17]],"date-time":"2012-05-17T00:00:00Z","timestamp":1337212800000},"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":[[2013,1]]},"DOI":"10.1007\/s00224-012-9413-4","type":"journal-article","created":{"date-parts":[[2012,5,16]],"date-time":"2012-05-16T02:45:31Z","timestamp":1337136331000},"page":"80-94","source":"Crossref","is-referenced-by-count":4,"title":["Time-Bounded Kolmogorov Complexity and Solovay Functions"],"prefix":"10.1007","volume":"52","author":[{"given":"Rupert","family":"H\u00f6lzl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thorsten","family":"Kr\u00e4ling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Merkle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,5,17]]},"reference":[{"issue":"6","key":"9413_CR1","doi-asserted-by":"crossref","first-page":"2099","DOI":"10.1090\/S0002-9939-09-09761-5","volume":"137","author":"G. Barmpalias","year":"2009","unstructured":"Barmpalias, G., Downey, R., Greenberg, N.: K-trivial degrees and the jump-traceability hierarchy. Proc. Am. Math. Soc. 137(6), 2099\u20132109 (2009)","journal-title":"Proc. Am. Math. Soc."},{"key":"9413_CR2","first-page":"1251","volume":"9","author":"J. Barzdin","year":"1968","unstructured":"Barzdin, J.: Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Sov. Math. Dokl. 9, 1251\u20131254 (1968)","journal-title":"Sov. Math. Dokl."},{"key":"9413_CR3","series-title":"A\u00a0Half-Century Survey","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-7091-6597-3_8","volume-title":"The Universal Turing Machine","author":"C.H. Bennett","year":"1995","unstructured":"Bennett, C.H.: Logical depth and physical complexity. In: The Universal Turing Machine, 2nd edn. A\u00a0Half-Century Survey, pp.\u00a0207\u2013235. Springer, Berlin (1995)","edition":"2"},{"key":"9413_CR4","first-page":"147","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"L. Bienvenu","year":"2009","unstructured":"Bienvenu, L., Downey, R.: Kolmogorov complexity and Solovay functions. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS), pp.\u00a0147\u2013158 (2009)"},{"issue":"5","key":"9413_CR5","doi-asserted-by":"crossref","first-page":"2045","DOI":"10.1016\/j.aim.2007.09.008","volume":"217","author":"P. Cholak","year":"2008","unstructured":"Cholak, P., Downey, R., Greenberg, N.: Strong jump-traceability I: the computably enumerable case. Adv. Math. 217(5), 2045\u20132074 (2008)","journal-title":"Adv. Math."},{"key":"9413_CR6","author":"R. Downey","year":"2011","unstructured":"Downey, R., Greenberg, N.: Strong jump-traceability II: K-triviality. Israel J. Math. (2011). doi: 10.1007\/s11856-011-0217-z","journal-title":"Israel J. Math."},{"key":"9413_CR7","series-title":"Theory and Applications of Computability","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic Randomness and Complexity","author":"R.G. Downey","year":"2010","unstructured":"Downey, R.G., Hirschfeldt, D.R.: Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, New York (2010)"},{"key":"9413_CR8","first-page":"392","volume-title":"Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science","author":"R. H\u00f6lzl","year":"2009","unstructured":"H\u00f6lzl, R., Kr\u00e4ling, T., Merkle, W.: Time-bounded Kolmogorov complexity and Solovay functions. In: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science, pp.\u00a0392\u2013402 (2009)"},{"issue":"1\u20132","key":"9413_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0304-3975(94)00014-X","volume":"132","author":"D.W. Juedes","year":"1994","unstructured":"Juedes, D.W., Lathrop, J.I., Lutz, J.H.: Computational depth and reducibility. Theor. Comput. Sci. 132(1\u20132), 37\u201370 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9413_CR10","doi-asserted-by":"crossref","first-page":"1123","DOI":"10.1137\/S0097539794268789","volume":"25","author":"M. Kummer","year":"1996","unstructured":"Kummer, M.: Kolmogorov complexity and instance complexity of recursively enumerable sets. SIAM J. Comput. 25(6), 1123\u20131143 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9413_CR11","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1137\/S0097539799357441","volume":"31","author":"A. Ku\u010dera","year":"2001","unstructured":"Ku\u010dera, A., Slaman, T.A.: Randomness and recursive enumerability. SIAM J. Comput. 31(1), 199\u2013211 (2001)","journal-title":"SIAM J. Comput."},{"key":"9413_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (2008)"},{"issue":"4","key":"9413_CR13","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1215\/00294527-2009-017","volume":"50","author":"J.S. Miller","year":"2010","unstructured":"Miller, J.S.: The K-degrees, low for K-degrees and weakly low for K-degrees. Notre Dame J. Form. Log. 50(4), 381\u2013391 (2010)","journal-title":"Notre Dame J. Form. Log."},{"key":"9413_CR14","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001","volume-title":"Computability and Randomness","author":"A. Nies","year":"2009","unstructured":"Nies, A.: Computability and Randomness. Oxford University Press, London (2009)"},{"key":"9413_CR15","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C.P. Schnorr","year":"1973","unstructured":"Schnorr, C.P.: Process complexity and effective random tests. J. Comput. Syst. Sci. 7, 376\u2013388 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"9413_CR16","unstructured":"Solovay, R.M.: Draft of paper (or series of papers) on Chaitin\u2019s work. Unpublished notes (1975)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9413-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9413-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9413-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:24Z","timestamp":1558684464000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9413-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,17]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["9413"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9413-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,17]]}}}