{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:56:46Z","timestamp":1787500606868,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_87","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:46:30Z","timestamp":1330177590000},"page":"23-34","source":"Crossref","is-referenced-by-count":33,"title":["Randomness, relativizations, and polynomial reducibilities"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"K.Ambos-Spies, Three theorems on polynomial degrees of NP-sets, Proc. FOCS 1985.","DOI":"10.1109\/SFCS.1985.61"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill and R. Solovay, Relativizations of the P=?NP question, SIAM J. Comput. 4(1975) 431\u2013442.","journal-title":"SIAM J. Comput."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"C.H. Bennett and J. Gill, Relative to a random oracle A, PA\u2260NPA\u2260co-NPA with probability 1, SIAM J. Comput. 10 (1981) 96\u2013113.","journal-title":"SIAM J. Comput."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"S.A.Cook, The complexity of theorem proving procedures, Proc. 3rd STOC 1971, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"3_CR5","volume-title":"An Introduction to Probability Theory and its Applications","author":"W. Feller","year":"1957","unstructured":"W. Feller, An Introduction to Probability Theory and its Applications, John Wiley, New York, 1957."},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput. 6 (1977) 675\u2013695.","journal-title":"SIAM J. Comput."},{"key":"3_CR7","unstructured":"J. Hartmanis, Solvable problems with conflicting relativizations, Bull. EATCS 27, October 1985."},{"key":"3_CR8","volume-title":"Introduction to Automata Theory","author":"J.E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Reading, MA., 1979."},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in \u201cComplexity of Computer Computations\u201d (R.E. Miller and J.W. Thatcher, Eds.), Plenum, New York, 1972, 85\u2013103."},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"S.A.Kurtz, On the random oracle hypothesis, Proc. 14th STOC 1982.","DOI":"10.1145\/800070.802195"},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"R.E. Ladner, On the structure of polynomial time reducibility, J. ACM 22 (1975) 155\u2013171.","journal-title":"J. ACM"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(81)90069-4","volume":"15","author":"L.H. Landweber","year":"1981","unstructured":"L.H. Landweber, R.J. Lipton and E.L. Robertson, On the structure of sets in NP and other complexity classes, Theor. Comp. Sci. 15 (1981) 181\u2013200.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"K.Mehlhorn, The \u201calmost all\u201d theory of subrecursive degrees is decidable, Tech. Rep. TR-73-170, 1973, Cornell University.","DOI":"10.1007\/978-3-662-21545-6_23"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"K.Mehlhorn, The \u201calmost all\u201d theory of subrecursive degrees is decidable, Proc. 2nd ICALP, Lecture Notes in Comp. Sci. 15 (1974), Springer Verlag.","DOI":"10.1007\/978-3-662-21545-6_23"},{"key":"3_CR15","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(76)80035-9","volume":"12","author":"K. Mehlhorn","year":"1976","unstructured":"K. Mehlhorn, Polynomial and abstract subrecursive classes, J. Comput. Sytem Sci. 12 (1976) 147\u2013178.","journal-title":"J. Comput. Sytem Sci."},{"key":"3_CR16","unstructured":"P.Orponen, Complexity of alternating machines with oracles, Proc. 10th ICALP, Lecture Notes in Comp. Sci. 154 (1983), Springer Verlag."},{"key":"3_CR17","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1967."},{"key":"3_CR18","unstructured":"G.E. Sacks, Degrees of Unsolvability, Second edition,Annals of Mathematics Studies Number 55, Princeton University Press, 1966."},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0304-3975(84)90124-5","volume":"31","author":"U. Sch\u00f6ning","year":"1984","unstructured":"U. Sch\u00f6ning, Minimal pairs for P, Theor. Comp. Sci. 31 (1984) 41\u201348.","journal-title":"Theor. Comp. Sci."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"R.I.Soare, Recursively Enumerable Sets and Degrees: The Study of Computable Functions and Computably Generated Sets, Springer Verlag (to appear).","DOI":"10.1007\/978-3-662-02460-7"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"J.Stillwell, Decidability of the \u201calmost all\u201d theory of degrees, J. Symbolic Logic, 1972.","DOI":"10.2307\/2272735"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_87.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T13:43:52Z","timestamp":1687268632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_87","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}