{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:21Z","timestamp":1725488601365},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_30","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:32:26Z","timestamp":1186727546000},"page":"311-322","source":"Crossref","is-referenced-by-count":2,"title":["Monte-Carlo Polynomial versus Linear Time - The Truth-Table Case"],"prefix":"10.1007","author":[{"given":"Robert","family":"Rettinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rutger","family":"Verbeek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(93)90117-C","volume":"115","author":"B. Allender","year":"1993","unstructured":"Allender, Beigel, Hertrampf, Homer, Almost-everywhere Complexity Hierarchies for Nondeterministic Time, TCS 115(1993), pp. 225\u2013241.","journal-title":"TCS"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Balcazar, Diaz, Gabarro, Structural Complexity 2, Springer 1990.","DOI":"10.1007\/978-3-642-75357-2"},{"key":"30_CR3","volume-title":"Technical Report TRITA-NA9702","author":"H. Berg","year":"1997","unstructured":"Berg, H\u00e5stad, On the BPP Hierarchy Problem, Technical Report TRITA-NA9702, Royal Inst. of Technology, Stockholm 1997."},{"key":"30_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume-title":"Proc. MFCS","author":"Freivalds","year":"1981","unstructured":"Freivalds, Probabilistic two-way Machines, Proc. MFCS, LNCS 118, Springer 1981, pp. 33\u201345."},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Fortnow, Sipser, Probabilistic Computation and Linear Time, ACM Symposium on Theory of Computing (STOC), 1989, pp. 148\u2013156.","DOI":"10.1145\/73007.73021"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Fortnow, Sipser, Retraction of Probabilistic Computation and Linear Time, ACM Symposium on Theory of Computing (STOC), 1997, p. 750.","DOI":"10.1145\/258533.258677"},{"issue":"4","key":"30_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/219817.219822","volume":"26","author":"Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, Complexity Theory Column 11, SIGACT News 26,4 (1995), pp. 5\u201315.","journal-title":"SIGACT News"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/0890-5401(87)90057-5","volume":"75","author":"V. Karpinski","year":"1987","unstructured":"Karpinski, Verbeek, 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":"30_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/3-540-18170-9_166","volume-title":"Computation Theory and Logic","author":"V. Karpinski","year":"1987","unstructured":"Karpinski, Verbeek, Randomness, Provability and the Separation of Monte Carlo Time and Space, Computation Theory and Logic, LNCS 270 (1987), pp. 189\u2013207."},{"key":"30_CR10","unstructured":"Rettinger, Orakelabh\u00e4ngige Zeithierarchies\u00e4tze, PhD thesis, FernUniversit\u00e4t Hagen, 1999."},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1137\/0210057","volume":"10","author":"S. Rackoff","year":"1981","unstructured":"Rackoff, Seiferas, Limitations on Separating Nondeterministic Complexity Classes, SIAM Journal on Computing 10 (1981), pp. 742\u2013745.","journal-title":"SIAM Journal on Computing"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Seiferas, Fischer, Meyer, Separating Nondeterministic Time Complexity Classes, JACM 25, pp. 146\u2013167.","DOI":"10.1145\/322047.322061"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:13:04Z","timestamp":1556734384000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}