{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T19:14:41Z","timestamp":1780600481716,"version":"3.54.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf00264313","type":"journal-article","created":{"date-parts":[[2004,9,29]],"date-time":"2004-09-29T06:07:21Z","timestamp":1096438041000},"page":"679-688","source":"Crossref","is-referenced-by-count":51,"title":["Sets with small generalized Kolmogorov complexity"],"prefix":"10.1007","volume":"23","author":[{"given":"Jos\ufffd L.","family":"Balc\ufffdzar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronald V.","family":"Book","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"Allender, E.: The complexity of sparse sets in P. Proc. Conference on Structure in Complexity Theory. Lect. Notes Comput, Sci. (233), pp. 1?11. Heidelberg, Berlin, New York: Springer"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(85)90168-9","volume":"40","author":"J. Balc\u00e1zar","year":"1985","unstructured":"Balc\u00e1zar, J., Book, R., Sch\u00f6ning, U.: On bounded query machines. Theor. Comput. Sci. 40, 237?243 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar, J., Book, R., Sch\u00f6ning, U.: Sparse sets, lowness, and highness, SIAM J. Comput. 15 (1986) (To appear). Also see: Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 176, 185?193 (1984)","DOI":"10.1007\/BFb0030298"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. Book","year":"1984","unstructured":"Book, R., Long, T., Selman, A.: Quantitative relativizations of complexity classes. SIAM J. Comput. 13, 461?487 (1984)","journal-title":"SIAM J. Comput."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G. Chaitin","year":"1966","unstructured":"Chaitin, G.: On the length of programs for computing finite binary sequences. J. Assoc. Comput. Mach. 13, 547?569 (1966)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1145\/321832.321839","volume":"21","author":"G. Chaitin","year":"1974","unstructured":"Chaitin, G.: Information-theoretic limitations of formal systems. J. Assoc, Comput. Mach. 21, 403?424 (1974)","journal-title":"J. Assoc, Comput. Mach."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G. Chaitin","year":"1975","unstructured":"Chaitin, G.: A theory of program size formally identical to information theory. J. Assoc. Comput. Mach. 22, 329?340 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: Generalized Kolmogorov complexity and the structure of feasible computations. Proc. 24th IEEE Symp. Found. Comput. Sci. 439?445 (1983)","DOI":"10.1109\/SFCS.1983.21"},{"key":"CR9","series-title":"Lect. Notes Comput. Sci. Vol. 210","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/3-540-16078-7_86","volume-title":"On sparse oracles separating feasible complexity classes. Proc. STACS 86","author":"J. Hartmanis","year":"1986","unstructured":"Hartmanis, J., Hemachandra, L.: On sparse oracles separating feasible complexity classes. Proc. STACS 86. Lect. Notes Comput. Sci. Vol. 210, pp. 321?333. Heidelberg, Berlin, New York: Springer 1986"},{"key":"CR10","unstructured":"Ko, K.: A definition of infinite pseudorandom sequences Theor. Comput. Sci. (To appeare) 11."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/0885-064X(85)90012-3","volume":"1","author":"K. Ko","year":"1985","unstructured":"Ko, K.: Continuous optimization problems and a polynomial hierarchy of real functions. J. Complexitu 1, 210?231 (1985)","journal-title":"J. Complexitu"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/0214003","volume":"14","author":"K. Ko","year":"1985","unstructured":"Ko, K., Sch\u00f6ning, U.: On circuit-size complexity and the low hierarchy in N P. SIAM J. Comput. 14, 41?51 (1985)","journal-title":"SIAM J. Comput."},{"key":"CR13","first-page":"1","volume":"1","author":"A. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.: Three approaches to the quantitative definition of information. Probl. Inf. Transon 1, 1?7 (1965)","journal-title":"Probl. Inf. Transon"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1137\/0214043","volume":"14","author":"T. Long","year":"1985","unstructured":"Long, T.: On restricting the size of oracles compared with restricting access to oracles. SIAM J. Comput. 14, 585?597 (1985)","journal-title":"SIAM J. Comput."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Long, T., Selman, A.: Relativizing complexity classes with sparse oracles. J. Assoc. Comput. Mach. (To appear)","DOI":"10.1145\/5925.5938"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Paul, W., Seiferas, J., Simon, J.: An information-theoretic approach to time bounds for on-line computation. Proc. 12th ACM Symp. Theory Comput. 357?367 (1980)","DOI":"10.1145\/800141.804685"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"Sch\u00f6ning, U.: A low- and a high-hierarchy in NP. J. Comput. Syst. Sci. 27, 14?28 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"CR18","volume-title":"Lect. Notes Comput. Sci. Vol. 211","author":"U. Sch\u00f6ning","year":"1986","unstructured":"Sch\u00f6ning, U.: Complexity and structure. Lect. Notes Comput. Sci. Vol. 211. Berlin, Heidelberg, New York: Springer 1986"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1137\/0212037","volume":"12","author":"A. Selman","year":"1983","unstructured":"Selman, A., Mei-rui, X., Book, R.: Positive relativizations of complexity classes. SIAM J. Comput. 12, 565?579 (1983)","journal-title":"SIAM J. Comput."},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. Proc. 15th ACM Symp. Theory Comput. 330?335 (1983)","DOI":"10.1145\/800061.808762"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00264313.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00264313\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00264313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T06:58:24Z","timestamp":1585897104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00264313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF00264313"],"URL":"https:\/\/doi.org\/10.1007\/bf00264313","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}