{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:13:46Z","timestamp":1743117226458,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648246"},{"type":"electronic","value":"9783540685357"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"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":[[1998]]},"DOI":"10.1007\/3-540-68535-9_18","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:31:22Z","timestamp":1193473882000},"page":"147-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Boolean Lowness and Boolean Highness"],"prefix":"10.1007","author":[{"given":"Steffen","family":"Reith","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus W.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,4]]},"reference":[{"key":"18_CR1","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. Ogihara. A relationship between difference hierarchies and relativized polynomial hierarchies. Mathematical Systems Theory, 26:293\u2013310, 1993.","journal-title":"Mathematical Systems Theory"},{"key":"18_CR2","unstructured":"H. Buhrmann and L. Fortnow. Two queries. TR 96-20, University of Chicago, Department of Computer Science, 1996."},{"issue":"6","key":"18_CR3","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"CGH+88_J.-Y. Cai","year":"1988","unstructured":"[CGH+88]_J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. 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"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-16486-3_93","volume":"223","author":"J. Cai","year":"1986","unstructured":"J. Cai and L. Hamachandra. The boolean hierarchy: Hardware over NP. Proceedings of the Structure in Complexity Theory Conference, 223:105\u2013124, 1986.","journal-title":"Proceedings of the Structure in Complexity Theory Conference"},{"key":"18_CR5","unstructured":"R. Chang. Bounded queries, approximation and the boolean hierarchy. TR CS 97-04, University of Maryland, Department of Computer Science and Electrical Engineering, 1997."},{"issue":"2","key":"18_CR6","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, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"655","DOI":"10.2307\/2272849","volume":"39","author":"S. B. Cooper","year":"1974","unstructured":"S. B. Cooper. Minimal pairs and high recursively enumerable degree. Journal of Symbolic Logic, 39:655\u2013660.","journal-title":"Journal of Symbolic Logic"},{"key":"18_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of the 14th STACS","author":"L. A. Hemaspaandra","year":"1997","unstructured":"L. A. Hemaspaandra, E. Hemaspaandra, and H. hempel. A downward translation in the polynomial hierarchy. In Proc. of the 14th STACS, volume 1200 of LNCS. Springer Verlag, 1997."},{"key":"18_CR9","unstructured":"L. A. Hemaspaandra, E. Hemaspaandra, and H. Hempel. Translating equality downwards. TR 657, University of Rochester, Department of Computer Science, 1997."},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"E. Hemaspaandra, L. Hemaspaandra, and H. hempel. What\u2019s up with downward collapse: Using the easy-hard technique to link boolean and polynomial hierarchy collapses. TR 682, University of Rochester, Department of Computer Science, February 1998.","DOI":"10.1145\/300307.300308"},{"issue":"6","key":"18_CR11","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.","journal-title":"SIAM Journal on Computing"},{"key":"18_CR12","unstructured":"J. K\u00f6bler. Untersuchungen verschiedener polynomieller Reduktionsklassen von NP. Diploma Thesis, Universit\u00e4t Stuttgart, 1985."},{"issue":"4","key":"18_CR13","doi-asserted-by":"publisher","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. W. Wagner. The difference and truth-table hierarchies for NP. R.A.I.R.O. Theoretical Informatics and Applications, 21(4):419\u2013435, 1987.","journal-title":"R.A.I.R.O. Theoretical Informatics and Applications"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning. A low and a high hierarchy within NP. Journal of Computer and System Sciences, 27:14\u201328, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR15","series-title":"Lect Notes Comput Sci","volume-title":"Complexity and Structure","author":"U. Sch\u00f6ning","year":"1985","unstructured":"U. Sch\u00f6ning. Complexity and Structure, volume 211 of LNCS. Springer-Verlag, 1985."},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/S0002-9904-1974-13350-1","volume":"80","author":"R. I. Soare","year":"1974","unstructured":"R. I. Soare. Automorphisms of the lattice of recursively enumerable sets. Bulletin of the American Mathematical Society, 80:53\u201358, 1974.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"18_CR17","unstructured":"K. W. Wagner. Number-of-query hierachies. TR 158, University of Augsburg, 1987."},{"key":"18_CR18","unstructured":"K. W. Wagner. A note on bounded queries and the difference hierarchy. TR 137, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, 1997."},{"key":"18_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BFb0028832","volume-title":"Proc. of the Conference of Foundations on Computation Theory","author":"G. Wechsung","year":"1985","unstructured":"G. Wechsung and K. Wagner. On the boolean closure of NP, manuscript. Extended abstract as: Wechsung, G., On the boolean closure of NP. In Proc. of the Conference of Foundations on Computation Theory, volume 199 of LNCS, pages 485\u2013493. Springer Verlag, 1985."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68535-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T09:53:36Z","timestamp":1589882016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68535-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648246","9783540685357"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-68535-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"4 June 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}