{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T20:55:43Z","timestamp":1773176143699,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540671411","type":"print"},{"value":"9783540465416","type":"electronic"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"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":[[2000]]},"DOI":"10.1007\/3-540-46541-3_13","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"157-168","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["The Boolean Hierarchy of NP-Partitions"],"prefix":"10.1007","author":[{"given":"Sven","family":"Kosub","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":[[2000,3,24]]},"reference":[{"issue":"6","key":"13_CR1","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J.-Y. Cai","year":"1988","unstructured":"J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. W. 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":"13_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-16486-3_93","volume-title":"Proceedings 1st Structure in Complexity Theory Conference","author":"J.-Y. Cai","year":"1986","unstructured":"J.-Y. Cai and L. Hemachandra. The Boolean hierarchy: hardware over NP. In Proceedings 1st Structure in Complexity Theory Conference, volume 223 of Lecture Notes in Computer Science, pages 105\u2013124. Springer-Verlag, 1986."},{"key":"13_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-7633-9","volume-title":"General Lattice Theory","author":"G. Gr\u00e4tzer","year":"1978","unstructured":"G. Gr\u00e4tzer. General Lattice Theory. Akademie-Verlag, Berlin, 1978."},{"issue":"4","key":"13_CR4","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1142\/S0129054195000214","volume":"6","author":"L. A. Hemaspaandra","year":"1995","unstructured":"L. A. Hemaspaandra, A. Hoene, A. V. Naik, M. Ogihara, A. L. Selman, T. Thierauf, and J. Wang. Nondeterministically selective sets. International Journal of Foundations of Computer Science, 6(4):403\u2013416, 1995.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"13_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/BFb0023834","volume-title":"Proceedings 1st Latin American Symposium on Theoretical Informatics","author":"U. Hertrampf","year":"1992","unstructured":"U. Hertrampf. Locally definable acceptance types \u2014 the three-valued case. In Proceedings 1st Latin American Symposium on Theoretical Informatics, volume 583 of Lecture Notes in Computer Science, pages 262\u2013271, Berlin, 1992. Springer-Verlag."},{"issue":"6","key":"13_CR6","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 in same journal 20(2):404, 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"13_CR7","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. W. Wagner. The difference and truth-table hierarchies for NP. RAIRO Theoretical Informatics and Applications, 21(4):419\u2013435, 1987.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"13_CR8","series-title":"Lect Notes Comput Sci","first-page":"485","volume-title":"Proceedings 5th International Conference on Fundamentals in Computation Theory","author":"K. W. Wagner","year":"1985","unstructured":"K. W. Wagner and G. Wechsung. On the boolean closure of NP. Extended abstract as: G. Wechsung. On the boolean closure of NP. Proceedings 5th International Conference on Fundamentals in Computation Theory, volume 199 of Lecture Notes in Computer Science, pages 485\u2013493, Berlin, 1985."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T11:57:59Z","timestamp":1578484679000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_13"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}