{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:52Z","timestamp":1725664132458},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_255","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:09:45Z","timestamp":1330261785000},"page":"250-258","source":"Crossref","is-referenced-by-count":0,"title":["Relativizing complexity classes with Random Oracles"],"prefix":"10.1007","author":[{"given":"Ronald V.","family":"Book","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. Randomness, relativizations, and polynomial reducibilities, Proc. 1st Conf. Structure in Complexity Theory, Lecture Notes in Computer Sci. 223, Springer-Verlag, 1986, 23\u201334.","DOI":"10.1007\/3-540-16486-3_87"},{"key":"27_CR2","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":"27_CR3","doi-asserted-by":"publisher","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, P\nA \u2260 NP\nA \u2260 co-NP\nA with probability 1, SIAM J. Computing 10 (1981), 96\u2013113.","journal-title":"SIAM J. Computing"},{"key":"27_CR4","unstructured":"R. Book, J. Lutz, and K. Wagner. An observation on probability versus randomness with applications to complexity classes, Math. Systems Theory 26 (1994), to appear. See also Proc. STACS 92, Lecture Notes in Computer Sci. 577, Springer-Verlag, 319\u2013328."},{"key":"27_CR5","unstructured":"S. Kautz. Degrees of Random Sets, Ph.D. Dissertation, Cornell University, 1991."},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vitanyi. Kolmogorov complexity and its applications, in J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, vol. A, Elsevier Sci. Publishers (1990), 187\u2013254.","DOI":"10.1016\/B978-0-444-88071-0.50009-6"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. Lutz","year":"1992","unstructured":"J. Lutz. Almost everywhere high nonuniform complexity, J. Comput. System Sci. 44 (1992), 220\u2013258.","journal-title":"J. Comput. System Sci."},{"key":"27_CR8","unstructured":"J. Lutz, A pseudorandom oracle characterization of BPP, SIAM J. Computing, 24 (1993), to appear. See also Proc. Sixth IEEE Conf. on Structure in Complexity Theory, 1991, 190\u2013195."},{"key":"27_CR9","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 (1966), 602\u2013619.","journal-title":"Info. and Control"},{"key":"27_CR10","doi-asserted-by":"publisher","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 Wahrscheinlichkeitstheory und Verwandte Gebiete 19 (1971), 225\u2013230.","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheory und Verwandte Gebiete"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson. Hardness vs. randomness, Proc. 29th IEEE Symp. Found. of Comput. Sci. (1988), 2\u201311.","DOI":"10.1109\/SFCS.1988.21916"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_255.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:06:21Z","timestamp":1619571981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_255","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}