{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:10:10Z","timestamp":1742595010655,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540552109"},{"type":"electronic","value":"9783540467755"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55210-3_193","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:53:31Z","timestamp":1330250011000},"page":"319-328","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On complexity classes and algorithmically random languages"],"prefix":"10.1007","author":[{"given":"Ronald V.","family":"Book","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. Randomness, relativations, and polynomial reducibilities. In Lecture Notes in Computer Sci. 223, pages 23\u201334. Proc. 1st Conf. Stucture in Complexity Theory, Springer-Verlag, 1986.","DOI":"10.1007\/3-540-16486-3_87"},{"key":"25_CR2","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1145\/5925.5937","volume":"33","author":"J. Balc\u00e1zar","year":"1986","unstructured":"J. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning. The polynomial-time hierarchy and sparse oracles. J. Assoc. Comput. Mach., 33:603\u2013617, 1986.","journal-title":"J. Assoc. Comput. Mach."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity II. Springer-Verlag, 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"C. Bennett. Logical depth and physical complexity. In R. Herken (ed.), The Universal Turing Machine: A Half-Century Survey, pages 227\u2013257. Oxford University Press, 1988.","DOI":"10.1093\/oso\/9780198537748.003.0008"},{"key":"25_CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill. Relative to a random oracle PA \u2260 NPA \u2260 co-NPA with probability 1. SIAM J. Computing, 10:96\u2013113, 1981.","journal-title":"SIAM J. Computing"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"J.-Y. Cai. Probability one separation of the boolean hierarchy. In Lecture Notes in Computer Sci. 38, pages 148\u2013158. STACS 87, Springer Verlag, 1987.","DOI":"10.1007\/BFb0039602"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/0022-0000(89)90033-0","volume":"38","author":"J.-Y. Cai","year":"1989","unstructured":"J.-Y. Cai. With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy. J. Comput. Systems Sci., 38:68\u201385, 1989.","journal-title":"J. Comput. Systems Sci."},{"key":"25_CR9","first-page":"191","volume":"28","author":"R. Karp","year":"1982","unstructured":"R. Karp and R. Lipton. Turing machines, that take advice. L'Enseignement Math\u00e9matique, 28 2nd series:191\u2013209, 1982.","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"25_CR10","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1145\/5925.5938","volume":"33","author":"T. Long","year":"1986","unstructured":"T. Long and A. Selman. Relativizing complexity classes with sparse oracles. J. Assoc. Comput. Mach., 33:618\u2013627, 1986.","journal-title":"J. Assoc. Comput. Mach."},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"P. Martin-L\u00f6f. On the definition of random sequences. Info. and Control, 9:602\u2013619, 1966.","journal-title":"Info. and Control"},{"key":"25_CR12","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00534110","volume":"19","author":"P. Martin-L\u00f6f","year":"1971","unstructured":"P. Martin-L\u00f6f. Complexity oscillations in infinite binary sequences. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete, 19:225\u2013230, 1971.","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"M. Ogiwara and A. Lozano. On one query self reducible sets. In Proc. 6th IEEE Conference on Structure in Complexity Theory, pages 139\u2013151, 1991.","DOI":"10.1109\/SCT.1991.160254"},{"key":"25_CR14","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and 0. Watanabe. On polynomial bounded truth table reducibility of NP sets to sparse sets. SIAM J. Computing, 20:471\u2013483, 1991.","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","STACS 92"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55210-3_193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:31:27Z","timestamp":1742592687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55210-3_193"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540552109","9783540467755"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-55210-3_193","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}