{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:48Z","timestamp":1725483768409},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_42","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"467-476","source":"Crossref","is-referenced-by-count":5,"title":["On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems"],"prefix":"10.1007","author":[{"given":"Sven","family":"Kosub","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"42_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. V. Book","year":"1984","unstructured":"R. V. Book, T. J. Long, and A. L. Selman. Quantitative relativizations of complexity classes. SIAM Journal on Computing, 13:461\u2013487, 1984.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"42_CR2","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0022-0000(85)90053-4","volume":"30","author":"R. V. Book","year":"1985","unstructured":"R. V. Book, T. J. Long, and A. L. Selman. Qualitative relativizations of complexity classes. Journal of Computer and System Sciences, 30(3):395\u2013413, 1985.","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"42_CR3","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":"42_CR4","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":"42_CR5","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":"42_CR6","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539794268315","volume":"25","author":"L. A. Hemaspaandra","year":"1996","unstructured":"L. A. Hemaspaandra, A. V. Naik, M. Ogihara, and A. L. Selman. Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing, 25(4):697\u2013708, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"L. A. Hemaspaandra, M. Ogihara, and G. Wechsung. Reducing the number of solutions of NP functions. In Proceedings 25th Symposium on Mathematical Foundations of Computer Science. These Proceedings.","DOI":"10.1007\/3-540-44612-5_35"},{"issue":"4","key":"42_CR8","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":"42_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-46541-3_13","volume-title":"Proceedings 17th Symposium on Theoretical Aspects of Computer Science","author":"S. Kosub","year":"2000","unstructured":"S. Kosub and K. W. Wagner. The boolean hierarchy of NP-partitions. In Proceedings 17th Symposium on Theoretical Aspects of Computer Science, volume 1770 of Lecture Notes in Computer Science, pages 157\u2013168, Berlin, 2000. Springer-Verlag."},{"issue":"1","key":"42_CR10","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(98)00060-7","volume":"207","author":"A. V. Naik","year":"1998","unstructured":"A. V. Naik, J. D. Rogers, J. S. Royer, and A. L. Selman. A hierarchy based on output multiplicity. Theoretical Computer Science, 207(1):131\u2013157, 1998.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"42_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(96)00030-0","volume":"58","author":"M. Ogihara","year":"1996","unstructured":"M. Ogihara. Functions computable with limited access to NP. Information Processing Letters, 58(1):35\u201338, 1996.","journal-title":"Information Processing Letters"},{"key":"42_CR12","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","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T15:18:18Z","timestamp":1550330298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_42","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}