{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:59:44Z","timestamp":1725663584814},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56939-1_75","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:55:01Z","timestamp":1330257301000},"page":"227-240","source":"Crossref","is-referenced-by-count":3,"title":["On randomized versus deterministic computation"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"Rutger","family":"Verbeek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"19_CR1","unstructured":"Adleman, L., Two Theorems on Random Polynomial Time, Proc. 19th IEEE FOCS, 1972, pp. 75\u201383."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Adleman, L., Manders, K., Reducibility, Randomness, and Intractibility, Proc. 9th ACM STOC, 1977, pp. 151\u2013163.","DOI":"10.1145\/800105.803405"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Allender, E., Beigel, R., Hertrampf, U., Homer, S., Almost-Everywhere Complexity Hierarchies for Nondeterministic Time, Manuscript, 1992; A preliminary version has appeared in Proc. STACS '90, LNCS 415, Springer-Verlag, 1990, pp. 1\u201311.","DOI":"10.1016\/0304-3975(93)90117-C"},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"Ch. H. Bennett","year":"1981","unstructured":"Bennett, Ch. H., Gill, J., Relative to a Random Oracle A, P A \u2260 N P A \u2260 co-N P A with Probability 1, SIAM J. on Computing 10, 1981, pp. 96\u2013113.","journal-title":"SIAM J. on Computing"},{"key":"19_CR5","unstructured":"Fortnow, L., Personal Communication, 1992."},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Sipser, M., Probabilistic Computation and Linear Time, Proc. 21st ACM STOC, 1989, pp. 148\u2013166.","DOI":"10.1145\/73007.73021"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Freivalds, R., Fast Probabilistic Algorithms, Proc. MFCS'79, LNCS 75, 1979, Springer-Verlag, pp. 57\u201369.","DOI":"10.1007\/3-540-09526-8_5"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Johnson, P.S., A Catalog of Complexity Classes, in Handbook of Theoretical Computer Science, Vol. A., Algorithms and Complexity, Elsevier-MIT Press, 1990, pp. 69\u2013161.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan, R., Circuit-Size Lower Bounds and Non-reducibility to Sparse Sets, Information and Control 55, 1982, pp. 40\u201346.","journal-title":"Information and Control"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/0890-5401(87)90057-5","volume":"75","author":"M. Karpinski","year":"1987","unstructured":"Karpinski, M., Verbeek, R., On the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes, Information and Computation 75, 1987, pp. 178\u2013189.","journal-title":"Information and Computation"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Verbeek, R., Randomness, Provability, and the Separation of Monte Carlo Time and Space, LNCS 270, Springer-Verlag, 1988, pp. 189\u2013207.","DOI":"10.1007\/3-540-18170-9_166"},{"key":"19_CR12","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C Rackoff","year":"1982","unstructured":"Rackoff, C, Relational Questions Involving Probabilistic Algorithms, J. ACM 29, 1982, pp. 261\u2013268.","journal-title":"J. ACM"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Sipser, M., A Complexity Theoretic Approach to Randomness, Proc. 15th ACM STOC, 1983, pp. 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"19_CR14","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"L. Stockmeyer","year":"1985","unstructured":"Stockmeyer, L., On Approximation Algorithms for #P, SIAM J. Comput. 14, 1985, pp. 849\u2013861.","journal-title":"SIAM J. Comput."},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Wilson, C., Relativized Circuit Complexity, 24th IEEE FOCS, 1983, pp. 329\u2013334.","DOI":"10.1109\/SFCS.1983.66"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Yao, A. C., Coherent Functions and Program Checkers, Proc. 22nd ACM STOC, 1990, pp. 84\u201394.","DOI":"10.1145\/100216.100226"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_75.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:07:31Z","timestamp":1605647251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_75"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_75","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}