{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:23Z","timestamp":1725483743572},"publisher-location":"Berlin, Heidelberg","reference-count":22,"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_35","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:28:20Z","timestamp":1178357300000},"page":"394-404","source":"Crossref","is-referenced-by-count":2,"title":["Reducing the Number of Solutions of NP Functions"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerd","family":"Wechsung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"issue":"3","key":"35_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1137\/0213030","volume":"13","author":"R. Book","year":"1984","unstructured":"R. Book, T. Long, and A. Selman. Quantitative relativizations of complexity classes. SIAM Journal on Computing, 13(3):461\u2013487, 1984.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"35_CR2","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0022-0000(85)90053-4","volume":"30","author":"R. Book","year":"1985","unstructured":"R. Book, T. Long, and A. 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":"2","key":"35_CR3","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(92)90125-Y","volume":"104","author":"D. Bovet","year":"1992","unstructured":"D. Bovet, P. Crescenzi, and R. Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104(2):263\u2013283, 1992.","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"35_CR4","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"},{"key":"35_CR5","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science","author":"A. Durand","year":"2000","unstructured":"A. Durand, M. Hermann, and P. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science. Springer-Verlag Lecture Notes in Computer Science, August\/September 2000. To appear."},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, A. Naik, and J. Rogers. On inverting onto functions. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pages 213\u2013222. IEEE Computer Society Press, May 1996.","DOI":"10.1109\/CCC.1996.507683"},{"key":"35_CR7","first-page":"93","volume":"63","author":"E. Hemaspaandra","year":"1997","unstructured":"E. Hemaspaandra, L. Hemaspaandra, and H. Hempel. An introduction to query order. Bulletin of the EATCS, 63:93\u2013107, 1997.","journal-title":"Bulletin of the EATCS"},{"issue":"2","key":"35_CR8","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1137\/S0097539796297632","volume":"28","author":"L. Hemaspaandra","year":"1999","unstructured":"L. Hemaspaandra, H. Hempel, and G. Wechsung. Query order. SIAM Journal on Computing, 28(2):637\u2013651, 1999.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"35_CR9","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539794268315","volume":"25","author":"L. Hemaspaandra","year":"1996","unstructured":"L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing, 25(4):697\u2013708, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"35_CR10","volume-title":"Technical Report TR-727","author":"L. Hemaspaandra","year":"2000","unstructured":"L. Hemaspaandra, M. Ogihara, and G. Wechsung. On reducing the number of solutions of NP functions. Technical Report TR-727, Department of Computer Science, University of Rochester, Rochester, NY, January 2000. Revised, March 2000."},{"issue":"11","key":"35_CR11","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1007\/s002360050109","volume":"34","author":"L. Hemaspaandra","year":"1997","unstructured":"L. Hemaspaandra, J. Rothe, and G. Wechsung. Easy sets and hard certificate schemes. Acta Informatica, 34(11):859\u2013879, 1997.","journal-title":"Acta Informatica"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"B. Jenner and J. Tor\u00e1n. The complexity of obtaining solutions for problems in NP. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_7"},{"key":"35_CR13","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science","author":"S. Kosub","year":"2000","unstructured":"S. Kosub. On NP-partitions over posets with an application to reducing the set of solutions of NP problems. In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science. Springer-Verlag Lecture Notes in Computer Science, August\/September 2000. To appear."},{"key":"35_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-46541-3_13","volume-title":"Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science","author":"S. Kosub","year":"2000","unstructured":"S. Kosub and K. Wagner. The boolean hierarchy of NP-partitions. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, pages 157\u2013168. Springer-Verlag Lecture Notes in Computer Science #1770, February 2000."},{"issue":"1","key":"35_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(98)00060-7","volume":"207","author":"A. Naik","year":"1998","unstructured":"A. Naik, J. Rogers, J. Royer, and A. Selman. A hierarchy based on output multiplicity. Theoretical Computer Science, 207(1):131\u2013157, 1998.","journal-title":"Theoretical Computer Science"},{"key":"35_CR16","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:35\u201338, 1996.","journal-title":"Information Processing Letters"},{"issue":"3","key":"35_CR17","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M. Ogiwara","year":"1993","unstructured":"M. Ogiwara and L. Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Sciences, 46(3):295\u2013325, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR18","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"},{"issue":"2","key":"35_CR19","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/S0022-0000(05)80009-1","volume":"48","author":"A. Selman","year":"1994","unstructured":"A. Selman. A taxonomy of complexity classes of functions. Journal of Computer and System Sciences, 48(2):357\u2013381, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR20","doi-asserted-by":"crossref","unstructured":"A. Selman. Much ado about functions. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pages 198\u2013212. IEEE Computer Society Press, May 1996.","DOI":"10.1109\/CCC.1996.507682"},{"issue":"2","key":"35_CR21","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1070\/IM1994v042n02ABEH001537","volume":"42","author":"N. Vereshchagin","year":"1994","unstructured":"N. Vereshchagin. Relativizable and nonrelativizable theorems in the polynomial theory of algorithms. Russian Academy of Sciences-Izvestiya-Mathematics, 42(2):261\u2013298, 1994.","journal-title":"Russian Academy of Sciences-Izvestiya-Mathematics"},{"issue":"1","key":"35_CR22","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(98)00024-6","volume":"66","author":"K. Wagner","year":"1998","unstructured":"K. Wagner. A note on parallel queries and the symmetric-difference hierarchy. Information Processing Letters, 66(1):13\u201320, 1998.","journal-title":"Information Processing Letters"}],"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_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T09:48:18Z","timestamp":1550310498000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_35","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}