{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:18:24Z","timestamp":1725455904050},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540626169"},{"type":"electronic","value":"9783540683421"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023469","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T02:06:33Z","timestamp":1132365993000},"page":"319-328","source":"Crossref","is-referenced-by-count":5,"title":["A downward translation in the polynomial hierarchy"],"prefix":"10.1007","author":[{"given":"Edith","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[]},{"given":"Harald","family":"Hempel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"issue":"1","key":"26_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF02090390","volume":"24","author":"E. Allender","year":"1991","unstructured":"E. Allender. Limitations of the upward separation technique. Mathematical Systems Theory, 24(1):53\u201367, 1991.","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"26_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(90)90099-4","volume":"75","author":"E. Allender","year":"1990","unstructured":"E. Allender and C. Wilson. Downward translations of equality. Theoretical Computer Science, 75(3):335\u2013346, 1990.","journal-title":"Theoretical Computer Science"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"A. Bertoni, D. Bruschi, D. Joseph, M. Sitharam, and P. Young. Generalized boolean hierarchies and boolean hierarchies over RP. In Proceedings of the 7th Conference on Fundamentals of Computation Theory, pages 35\u201346. Springer-Verlag Lecture Notes in Computer Science #380, August 1989.","DOI":"10.1007\/3-540-51498-8_4"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF01371729","volume":"26","author":"R. Beigel","year":"1993","unstructured":"R. Beigel, R. Chang, and M. Ogiwara. A relationship between difference hierarchies and relativized polynomial hierarchies. Mathematical Systems Theory, 26:293\u2013310, 1993.","journal-title":"Mathematical Systems Theory"},{"key":"26_CR5","unstructured":"H. Buhrman and L. Fortnow. Two queries. Manuscript, September 1996."},{"issue":"4","key":"26_CR6","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3(4):307\u2013318, 1993.","journal-title":"Computational Complexity"},{"issue":"3","key":"26_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1142\/S0129054190000151","volume":"1","author":"D. Bruschi","year":"1990","unstructured":"D. Bruschi, D. Joseph, and P. Young. Strong separations for the boolean hierarchy over RP. International Journal of Foundations of Computer Science, 1(3):201\u2013218, 1990.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. Book","year":"1974","unstructured":"R. Book. Tally languages and complexity classes. Information and Control, 26:186\u2013193, 1974.","journal-title":"Information and Control"},{"issue":"6","key":"26_CR9","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232\u20131252, 1988.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"26_CR10","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95\u2013111, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR11","volume-title":"PhD thesis","author":"R. Chang","year":"1991","unstructured":"R. Chang. On the Structure of NP Computations under Boolean Operators. PhD thesis, Cornell University, Ithaca, NY, 1991."},{"issue":"2","key":"26_CR12","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539790178069","volume":"25","author":"R. Chang","year":"1996","unstructured":"R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing, 25(2):340\u2013354, 1996.","journal-title":"SIAM Journal on Computing"},{"issue":"2\/3","key":"26_CR13","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis, N. Immerman, and V. Sewelson. Sparse sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, 65(2\/3):159\u2013181, 1985.","journal-title":"Information and Control"},{"issue":"1","key":"26_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1119","volume":"121","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and S. Jha. Defying upward and downward separation. Information and Computation, 121(1):1\u201313, 1995.","journal-title":"Information and Computation"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"L. Hemaspaandra and J. Rothe. Unambiguous computation: Boolean hierarchies and sparse Turing-complete sets. SIAM Journal on Computing. To appear.","DOI":"10.1137\/S0097539794261970"},{"key":"26_CR16","volume-title":"Technical Report Math\/95\/5","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra, J. Rothe, and G. Wechsung. Easy sets and hard certificate schemes. Technical Report Math\/95\/5, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t-Jena, Jena, Germany, May 1995."},{"issue":"4","key":"26_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/219817.219822","volume":"26","author":"L. Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra, A. Ramachandran, and M. Zimand. Worlds to die for. SIGACT News, 26(4):5\u201315, 1995.","journal-title":"SIGACT News"},{"issue":"6","key":"26_CR18","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"J. Kadin. The polynomial time hierarchy collapses if the boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263\u20131282, 1988. Erratum appears in the same journal, 20(2):404.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"26_CR19","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1137\/0218027","volume":"18","author":"K. Ko","year":"1989","unstructured":"K. Ko. Relativized polynomial time hierarchies having exactly k levels. SIAM Journal on Computing, 18(2):392\u2013408, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR20","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J. K\u00f6bler","year":"1987","unstructured":"J. K\u00f6bler, U. Sch\u00f6ning, and K. Wagner. The difference and truth-table hierarchies for NP. RAIRO Theoretical Informatics and Applications, 21:419\u2013435, 1987.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"issue":"4","key":"26_CR21","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0020-0190(94)90123-6","volume":"52","author":"R. Rao","year":"1994","unstructured":"R. Rao, J. Rothe, and O. Watanabe. Upward separation for FewP and related classes. Information Processing Letters, 52(4):175\u2013180, 1994.","journal-title":"Information Processing Letters"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"G. Wechsung. On the boolean closure of NP. In Proceedings of the 5th Conference on Fundamentals of Computation Theory, pages 485\u2013493. Springer-Verlag Lecture Notes in Computer Science #199, 1985. (An unpublished precursor of this paper was coauthored by K. Wagner).","DOI":"10.1007\/BFb0028832"}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T17:41:37Z","timestamp":1549302097000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0023469","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}