{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:49:41Z","timestamp":1725662981151},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540181705"},{"type":"electronic","value":"9783540477952"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18170-9_166","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:29:17Z","timestamp":1330180157000},"page":"189-207","source":"Crossref","is-referenced-by-count":8,"title":["Randomness, provability, and the separation of Monte Carlo Time and space"],"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,6,1]]},"reference":[{"key":"18_CR1","unstructured":"Adleman, L., Two Theorems on Random Polynomial Time Proc. 19th IEEE FOCS (1978), pp. 75\u201383"},{"key":"18_CR2","unstructured":"Adleman, L., and Manders, K., Reducibility, Randomness and Intractability Proc. 9th ACM STOC (1977), pp. 151\u2013163"},{"key":"18_CR3","unstructured":"Ajtai, M., and Ben-Or, M., A Theorem on Probabilistic Constant Depth Computations Proc. 16th ACM STOC (1984), pp. 471\u2013474"},{"key":"18_CR4","unstructured":"Ajtai, M., and Wigderson, A., Deterministic Simulation of Probabilistic Constant Depth Circuits Proc. 26th IEEE FOCS (1985), pp. 11\u201319"},{"key":"18_CR5","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., and Rackoff, C., Random Walks, Traversal Sequences and the Complexity of Maze Problems Proc. 20th IEEE FOCS (1979), pp. 218\u2013223"},{"key":"18_CR6","first-page":"42","volume":"6","author":"Y. Barzdin","year":"1962","unstructured":"Barzdin, Ya.M., On One Class of Turing Machines (Minsky Machines) Algebra and Logic Seminar, Novosibirsk 6, (1962), pp. 42\u201351 (Russian)","journal-title":"Algebra and Logic Seminar, Novosibirsk"},{"key":"18_CR7","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A. Borodin","year":"1983","unstructured":"Borodin, A., Cook, S., and Pippenger, N., Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines Information and Control 58 (1983), pp. 113\u2013136","journal-title":"Information and Control"},{"key":"18_CR8","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennet","year":"1981","unstructured":"Bennet, C., and Gill, J., Relative to a Random Oracle A, P\nA\n\u2260 NP\n\n                  A\n                \n\u2260 co-NP\n\n                  A\n                \nwith Probability 1 SIAM J. Comput. 10 (1981), pp. 96\u2013114","journal-title":"SIAM J. Comput."},{"key":"18_CR9","unstructured":"Babai, L., Grigoryev, D.Yu., and Mound, D.M., Isomorphism of Graphs with Bounded Eigenvalue Multiplicity Proc. 14th ACM STOC (1982), pp. 310\u2013324"},{"key":"18_CR10","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., Gill, J., and Solovay, R., Relativizations of the P = NP? question SIAM J. Comput. 4 (1975), pp. 431\u2013442","journal-title":"SIAM J. Comput."},{"key":"18_CR11","unstructured":"Berman, P., and Simon, J., Lower Bounds on Graph Threading by Probabilistic Machines Proc. 24th IEEE FOCS (1983), pp. 304\u2013311"},{"key":"18_CR12","unstructured":"Cook, S.A., The Complexity of Theorem-Proving Procedures Proc. 3rd ACM STOC (1971), pp. 151\u2013158"},{"key":"18_CR13","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"Cook, S.A., A Hierarchy for Non-deterministic Time Complexity J. Comput. System Sci. 7 (1973), pp. 343\u2013353","journal-title":"J. Comput. System Sci."},{"key":"18_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(85)80040-1","volume":"64","author":"S.A. Cook","year":"1985","unstructured":"Cook, S.A., A Taxonomy of Problems with Fast Parallel Algorithms Information and Control 64 (1985), pp. 1\u201322","journal-title":"Information and Control"},{"key":"18_CR15","volume-title":"An Introduction to Probability Theory and its Applications","author":"W. Feller","year":"1957","unstructured":"Feller, W., An Introduction to Probability Theory and its Applications John Wiley, New York 1957"},{"key":"18_CR16","first-page":"33","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"Freivalds, R., Probabilistic Two-Way Machines, MFCS '81 Springer LNCS 118 (1981), pp. 33\u201345","journal-title":"Springer LNCS"},{"key":"18_CR17","unstructured":"F\u00fcrer, M., The Tight Deterministic Time Hierarchy Proc. 14th ACM STOC (1982), pp. 8\u201316"},{"key":"18_CR18","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J., Computational Complexity of Probabilistic Turing Machines SIAM J. Comput. 6 (1977), pp. 675\u2013694","journal-title":"SIAM J. Comput."},{"key":"18_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness W.H. Freeman, San Francisco (1979)"},{"key":"18_CR20","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L.M. Goldschlager","year":"1977","unstructured":"Goldschlager, L.M., The Monotone and Planar Circuit Value Problema are Log Space Complete for P SIGACT News 9 (1977), pp. 25\u201329","journal-title":"SIGACT News"},{"key":"18_CR21","first-page":"121","volume":"226","author":"J. Hartmanis","year":"1986","unstructured":"Hartmanis, J. and Hemachandra, M., Complexity Classes without Machines: On Complete Languages for UP Proc. 13th ICALP '86, Springer, LNCS 226 (1986), pp. 121\u2013135","journal-title":"Springer, LNCS"},{"issue":"8","key":"18_CR22","doi-asserted-by":"crossref","first-page":"1793","DOI":"10.1002\/j.1538-7305.1967.tb03172.x","volume":"46","author":"J.E. Hopcroft","year":"1967","unstructured":"Hopcroft, J.E., and Ullman, J.D., An Approach to a Unified Theory of Automata The Bell System Technical J., vol. 46, no. 8, (1967), pp. 1793\u20131829","journal-title":"The Bell System Technical J."},{"key":"18_CR23","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., and Ullman, J.D., Introduction to Automata Theory, Languages, and Computation Addison-Wesley, Reading, Ma., (1979)"},{"key":"18_CR24","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1145\/321724.321727","volume":"19","author":"O.H. Ibarra","year":"1972","unstructured":"Ibarra, O.H., A Note Concerning Non-deterministic Tape Complexities J. ACM 19 (1972), pp. 608\u2013612","journal-title":"J. ACM"},{"key":"18_CR25","first-page":"281","volume":"172","author":"H. Jung","year":"1984","unstructured":"Jung, H., On Probabilistic Tape Complexity and Fast Circuits for Matrix Inversion Problems Proc. 11th ICALP '84, Springer LNCS 172 (1984), pp 281\u2013291","journal-title":"Proc. 11th ICALP '84, Springer LNCS"},{"key":"18_CR26","unstructured":"Karp, R.M., Upfal, E., and Wigderson, A., Are Search and Decision Problems Computationally Equivalent Proc. 17th ACM STOC (1985), pp. 464\u2013475"},{"key":"18_CR27","unstructured":"Karpinski, M., and Verbeek, R., On the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes Research Report #854-CS, University of Bonn (1986), submitted to Information and Control"},{"key":"18_CR28","unstructured":"Karpinski, M., and Verbeek, R., Randomised NC-Classes and the Provably Randomised Circuit Value Problem Research Report # 8511-CS, University of Bonn (1987), to be submitted"},{"key":"18_CR29","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E., The Circuit Value Problem is Log Space Complete for P SIGACT News 7 (1975), pp. 18\u201320","journal-title":"SIGACT News"},{"key":"18_CR30","unstructured":"Lewis, P.M., Stearns, R.E., and Hartmanis, J., Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages Proc. 6th IEEE Symp. on Switching Circuit Theory and Logical Design (1965), pp. 191\u2013202"},{"key":"18_CR31","doi-asserted-by":"crossref","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"M.L. Minsky","year":"1961","unstructured":"Minsky, M.L., Recursive Unsolvability of Post's Problem of \u2018Tag\u2019 and Other Topics in the Theory of Turing Machines Annals of Math. 74 (1961), pp. 437\u2013455","journal-title":"Annals of Math."},{"key":"18_CR32","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"Rackoff, C., Relativized Questions Involving Probabilistic Algorithms J. ACM 29 (1982), pp. 261\u2013268","journal-title":"J. ACM"},{"key":"18_CR33","first-page":"1","volume-title":"The Theory of Recursive Functions and Effective Computability","author":"H. Rogers","year":"1967","unstructured":"Rogers, H., The Theory of Recursive Functions and Effective Computability McGraw-Hill, New York (1967), pp. 1\u2013482"},{"key":"18_CR34","unstructured":"Ruby, S., and Fischer, P.C., Translational Methods in Computational Complexity IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor (1965), pp. 173\u2013178"},{"key":"18_CR35","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0022-0000(77)80041-X","volume":"14","author":"J.I. Seiferas","year":"1977","unstructured":"Seiferas, J.I., Techniques for Separating Space Complexity Classes J. Comput. System Sci. 14 (1977), pp. 73\u201399","journal-title":"J. Comput. System Sci."},{"key":"18_CR36","first-page":"521","volume":"140","author":"M. Sipser","year":"1982","unstructured":"Sipser, M., On Relativization and the Existence of Complete Sets Proc. 9th ICALP '82, Springer LNCS 140 (1982), pp. 521\u2013531","journal-title":"Proc. 9th ICALP '82, Springer LNCS"},{"key":"18_CR37","unstructured":"Sipser, M., Borel Sets and Circuit Complexity Proc. 15th ACM STOC (1983), pp. 61\u201369"},{"key":"18_CR38","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"Solovay, R., and Strassen, V., A Fast Monte Carlo Test for Primality SIAM J. Comput. 6 (1977), pp. 84\u201385","journal-title":"SIAM J. Comput."},{"key":"18_CR39","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0166-218X(83)90023-9","volume":"5","author":"D.J.A. Welsh","year":"1983","unstructured":"Welsh, D.J.A., Randomised Algorithms Discrete Applied Mathematics 5 (1983), pp. 133\u2013145","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Computation Theory and Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18170-9_166.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T17:14:13Z","timestamp":1619543653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18170-9_166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540181705","9783540477952"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/3-540-18170-9_166","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}