{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:36:25Z","timestamp":1725456985392},"publisher-location":"Berlin\/Heidelberg","reference-count":15,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032039","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"283-293","source":"Crossref","is-referenced-by-count":2,"title":["Additional queries to random and pseudorandom oracles"],"prefix":"10.1007","author":[{"given":"Ronald V.","family":"Book","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]},{"given":"Shouwen","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","unstructured":"A. Amir, R. Beigel, and W. I. Gasarch, Cheatable, p-terse, and p-superterse sets, Proceedings of the Fifth Structure in Complexity Theory Conference, 1990, to appear."},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/0217056","volume":"17","author":"R. V. Book","year":"1988","unstructured":"R. V. Book and K. Ko, On sets truth-table reducible to sparse sets, SIAM Journal on Computing 17 (1988), pp. 903\u2013919.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G. J. Chaitin","year":"1975","unstructured":"G. J. Chaitin, A theory of program size formally identical to information theory, Journal of the Association for Computing Machinery 22 (1975), pp. 329\u2013340.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01084088","volume":"6","author":"R. I. Freidzon","year":"1976","unstructured":"R. I. Freidzon, Families of recursive predicates of measure zero, translated in Journal of Soviet Mathematics 6 (1976), pp. 449\u2013455, 1972.","journal-title":"Journal of Soviet Mathematics"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"P. R. Halmos, Measure Theory, Springer-Verlag, 1950.","DOI":"10.1007\/978-1-4684-9440-2"},{"key":"23_CR6","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, N. Lynch, and A. L. Selman, A comparison of polynomial-time reducibilities, Theoretical Computer Science 1 (1975), pp. 103\u2013123.","journal-title":"Theoretical Computer Science"},{"key":"23_CR7","first-page":"1413","volume":"14","author":"L. A. Levin","year":"1973","unstructured":"L. A. Levin, On the notion of a random sequence, Soviet Mathematics Doklady 14 (1973), pp. 1413\u20131416.","journal-title":"Soviet Mathematics Doklady"},{"key":"23_CR8","unstructured":"J. H. Lutz, Resource-bounded category and measure in complexity classes, Ph.D. dissertation, California Institute of Technology, 1987. Also see, Category and measure in complexity classes, SIAM Journal on Computing, to appear."},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"J. H. Lutz, Almost everywhere high nonuniform complexity, Proceedings of the Fourth Structure in Complexity Theory Conference, pp. 37\u201353, 1989.","DOI":"10.1109\/SCT.1989.41813"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"J. H. Lutz, Pseudorandom sources for BPP, Journal of Computer and System Sciences 40, 1990, to appear.","DOI":"10.1016\/0022-0000(90)90023-E"},{"key":"23_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, Information and Control 9 (1966), pp. 602\u2013619.","journal-title":"Information and Control"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, The \u201calmost all\u201d theory of subrecursive degrees is decidable, Proceedings of the Second Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science (1974), pp. 317\u2013325.","DOI":"10.1007\/3-540-06841-4_70"},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr, Process complexity and effective random tests, Journal of Computer and System Sciences 7 (1973), pp. 376\u2013388.","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"S. Tang and R. V. Book, Polynomial-time reducibilities and \u201calmost-all\u201d oracle sets, Theoretical Computer Science, 1990, to appear.","DOI":"10.1016\/0304-3975(91)90314-R"},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"O. Watanabe, A comparison of polynomial time completeness notions, Theoretical Computer Science 54 (1987), pp. 249\u2013265.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0032039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T13:44:41Z","timestamp":1586612681000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0032039","relation":{},"subject":[]}}