{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:22Z","timestamp":1725663262779},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_4","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:01:54Z","timestamp":1330203714000},"page":"35-46","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Generalized Boolean hierarchies and Boolean hierarchies over RP"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Bertoni","sequence":"first","affiliation":[]},{"given":"Danilo","family":"Bruschi","sequence":"additional","affiliation":[]},{"given":"Deborah","family":"Joseph","sequence":"additional","affiliation":[]},{"given":"Meera","family":"Sitharam","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Young","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"4_CR1","unstructured":"J. Addison, \u201cThe method of alternating chains,\u201d Symp Theor Models, North-Holland, (1965), 1\u201316."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"L. Adleman and M. A. Huang, \u201cRecognizing primes in random polynomial time,\u201d ACM Symp Theory Computing, (1987), 462\u2013469.","DOI":"10.1145\/28395.28445"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1137\/0215083","volume":"15","author":"E. Bach","year":"1986","unstructured":"E. Bach, G. Miller and J. Shallit, \u201cSums of divisors, perfect numbers and factoring,\u201d SIAM J Computing, 15, (1986), 1143\u20131154.","journal-title":"SIAM J Computing"},{"key":"4_CR4","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, \u201cRelativizations of the P = NP question,\u201d SIAM J Computing, 4 (1975), 431\u2013442.","journal-title":"SIAM J Computing"},{"key":"4_CR5","unstructured":"R. Beigel, \u201cBounded queries to SAT and the Boolean hierarchy,\u201d preprint, (1987)."},{"key":"4_CR6","unstructured":"R. Beigel, L. Hemachandra and G. Wechsung, \u201cOn the power of probabilistic polynomial time: P\n\n                  N P[log]\n                \n\n                  \n                    \n                  \n                  \n$$ \\subseteq $$\n\n                \nPP,\u201d Structure on Complexity Conference, (1989), to appear."},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennet","year":"1981","unstructured":"C. Bennet and J. Gill, \u201cRelative to a random oracle A, P\n\n                  A\n                \n\u2260 NP\n\n                  A\n                \n\u2260 coNP\n\n                  A\n                 with probability one,\u201d SIAM J Computing, 10 (1981), 96\u2013113.","journal-title":"SIAM J Computing"},{"key":"4_CR8","first-page":"1","volume":"809","author":"A. Bertoni","year":"1989","unstructured":"A. Bertoni, D. Bruschi, D. Joseph, M. Sitharam and P. Young, \u201cGeneralized Boolean hierarchies and Boolean hierarchies over RP,\u201d Univ Wisconsin, CS Dept Tech Report, 809 (1989), 1\u201350.","journal-title":"Univ Wisconsin, CS Dept Tech Report"},{"key":"4_CR9","first-page":"1","volume":"847","author":"D. Bruschi","year":"1989","unstructured":"D. Bruschi, D. Joseph and P. Young, \u201cStrong separations for the Boolean hierarchy over RP,\u201d Univ Wisconsin, CS Dept Tech Report, 847 (1989), 1\u201312.","journal-title":"Univ Wisconsin, CS Dept Tech Report"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"S.Buss and L. Hay, \u201cOn truth-table reducibility to SAT and the difference hierarchy,\u201d Structure in Complexity Conference, (1988), 224\u2013233.","DOI":"10.1109\/SCT.1988.5282"},{"key":"4_CR11","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"6","author":"J. Cai","year":"1988","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung, \u201cThe Boolean hiearchy I: structural properties,\u201d SIAM J Comput, 6 (1988), 1232\u20131252.","journal-title":"SIAM J Comput"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"7","author":"J. Cai","year":"1989","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung, \u201cThe Boolean hiearchy II: applications,\u201d SIAM J Comput, 7 (1989), 95\u2013111.","journal-title":"SIAM J Comput"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"J. Cai and L. Hemachandra, \u201cThe Boolean hierarchy: hardware over NP,\u201d Structure in Complexity Conference, (1986), 105\u2013124.","DOI":"10.1007\/3-540-16486-3_93"},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02218750","volume":"7","author":"Y. Ershov","year":"1968","unstructured":"Y. Ershov, \u201cA hierarchy of sets, I,\u201d Algebra and Logic, 7 (1968), 25\u201343.","journal-title":"Algebra and Logic"},{"key":"4_CR15","first-page":"15","volume":"7","author":"Y. Ershov","year":"1968","unstructured":"Y. Ershov, \u201cA hierarchy of sets, II,\u201d Algebra and Logic, 7 (1968), 15\u201347.","journal-title":"Algebra and Logic"},{"key":"4_CR16","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BF02219847","volume":"9","author":"Y. Ershov","year":"1969","unstructured":"Y. Ershov, \u201cA hierarchy of sets, III,\u201d Algebra and Logic, 9 (1969), 20\u201331.","journal-title":"Algebra and Logic"},{"key":"4_CR17","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1137\/0215035","volume":"15","author":"J. Geske","year":"1986","unstructured":"J. Geske and J. Grollmann, \u201cRelativizations of unambiguous and random polynomial time classes,\u201d SIAM J Computing, 15 (1986), 511\u2013519.","journal-title":"SIAM J Computing"},{"key":"4_CR18","first-page":"396","volume":"233","author":"T. Gundermann","year":"1986","unstructured":"T. Gundermann and G. Wechsung, \u201cNondeterministic Turing machines with modified acceptance,\u201d Proc MFCS, L N CS, 233 (1986), 396\u2013404.","journal-title":"Proc MFCS, L N CS"},{"key":"4_CR19","unstructured":"F. Hausdorff, Set Theory, Chelsea, 3rd ed., 1978."},{"key":"4_CR20","first-page":"159","volume":"1141","author":"P. Hinman","year":"1984","unstructured":"P. Hinman and S. Zachos, \u201cProbabilistic machines, oracles and quantifiers,\u201d Proc. Recursion Theory Week, L. N. Math. 1141 (1984), 159\u2013192.","journal-title":"L. N. Math."},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"J. Kadin, \u201cThe polynomial time hierarchy collapses if the Boolean hierarchy collapses,\u201d Structure in Complexity Conference, (1988), 278\u2013292.","DOI":"10.1109\/SCT.1988.5287"},{"key":"4_CR22","first-page":"419","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning and K. Wagner, \u201cThe difference and truth-table hierarchies for NP,\u201d RAIRO, 21 (1987), 419\u2013435.","journal-title":"RAIRO"},{"key":"4_CR23","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(82)90139-9","volume":"14","author":"K. Ko","year":"1982","unstructured":"K. Ko, \u201cSome observations on probabilistic algorithms and NP-hard problems,\u201d Inform Proc Letters, 14 (1982), 39\u201343.","journal-title":"Inform Proc Letters"},{"key":"4_CR24","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1983","unstructured":"C. Lautemann, \u201cBPP and the polynomial hierarchy,\u201d Inform Proc Letters, 17 (1983), 215\u2013217.","journal-title":"Inform Proc Letters"},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"49","DOI":"10.2307\/2270581","volume":"30","author":"H. Putnam","year":"1965","unstructured":"H. Putnam, \u201cTrial and error predicates and a solution to a problem of Mostowski,\u201d J Sym Logic, 30 (1965), 49\u201357.","journal-title":"J Sym Logic"},{"key":"4_CR26","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M. Rabin","year":"1980","unstructured":"M. Rabin, \u201cProbabilistic tests for primality,\u201d J Number Theory, 12 (1980), 128\u2013138.","journal-title":"J Number Theory"},{"key":"4_CR27","unstructured":"M. Rabin and J. Shallit, \u201cRandomized algorithms in number theory,\u201d To appear Comm Pure Appl Math."},{"key":"4_CR28","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"C. Rackoff, \u201cRelativized questions involving probabilistic algorithms,\u201d JACM, 29 (1982), 261\u2013268.","journal-title":"JACM"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"J. Schwartz, \u201cFast probabilistic algorithms for the verification of polynomial identities,\u201d JACM, 27 (1980), 701\u2013717.","journal-title":"JACM"},{"key":"4_CR30","doi-asserted-by":"crossref","unstructured":"M. Sipser, \u201cA complexity theoretic approach to randomness,\u201d Proc Symp Theory Comput, (1983), 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"4_CR31","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"R. Solovay and V. Strassen, \u201cA fast Monte-Carlo test for primality,\u201d SIAM J Comput 6 (1977), 84\u201385; [Erratum: 7 (1978), 118].","journal-title":"SIAM J Comput"},{"key":"4_CR32","first-page":"434","volume":"226","author":"K. Wagner","year":"1986","unstructured":"K. Wagner, \u201cMore complicated questions about maxima and minima, and some closure properties of NP,\u201d ICALP, L N Comp Sc, 226 (1986), 434\u2013443.","journal-title":"ICALP, L N Comp Sc"},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"K. Wagner, \u201cBounded query computations,\u201d Structure in Complexity Conference, (1988), 260\u2013277.","DOI":"10.1109\/SCT.1988.5286"},{"key":"4_CR34","first-page":"485","volume":"199","author":"G. Wechsung","year":"1985","unstructured":"G. Wechsung and K. Wagner, \u201cOn the Boolean closure of NP,\u201d Proc Conf Fundament Comput Theory, L N Comp Sc, 199 (1985), 485\u2013493.","journal-title":"L N Comp Sc"},{"key":"4_CR35","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S. Zachos","year":"1986","unstructured":"S. Zachos and H. Heller, \u201cA decisive characterization of BPP,\u201d Information and Control, 69 (1986), 125\u2013135.","journal-title":"Information and Control"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"S. Zachos, \u201cProbabilistic quantifiers, adversaries and complexity classes: an overview,\u201d Structure in Complexity Conference, (1986), 383\u2013400.","DOI":"10.1007\/3-540-16486-3_112"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:19:21Z","timestamp":1578536361000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_4"}},"subtitle":["Conference abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"28 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}