{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:27:13Z","timestamp":1757543233431},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583257"},{"type":"electronic","value":"9783540486534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58325-4_166","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:46:24Z","timestamp":1330253184000},"page":"56-64","source":"Crossref","is-referenced-by-count":4,"title":["Computing solutions uniquely collapses the polynomial hierarchy"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashish V.","family":"Naik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan L.","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"K. Abrahamson, M. Fellows, and C. Wilson. Parallel self-reducibility. In Proc. 4th ICCI, pages 67\u201370. IEEE Press, 1992.","DOI":"10.1109\/ICCI.1992.227703"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1137\/0215053","volume":"15","author":"J. Balc\u00e1zar","year":"1986","unstructured":"J. Balc\u00e1zar, R. Book, and U. Sch\u00f6ning. Sparse sets, lowness and highness. SIAM J. Comput., 15:739\u2013746, 1986.","journal-title":"SIAM J. Comput."},{"key":"8_CR3","unstructured":"H. Buhrman, J. Kadin, and T. Thierauf. On functions computable with nonadaptive queries to NP. In Proc. 9th STRUCTURES IEEE Press, 1992. To appear."},{"key":"8_CR4","doi-asserted-by":"crossref","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 J. Comput., 13:461\u2013487, 1984.","journal-title":"SIAM J. Comput."},{"key":"8_CR5","unstructured":"R. Book. Manuscript."},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(93)90146-Z","volume":"48","author":"H. Buhrman","year":"1993","unstructured":"H. Buhrman, L. Torenvliet, and P. van Emde Boas. Twenty questions to a P-selector. IPL, 48:201\u2013204, 1993.","journal-title":"IPL"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"H. Buhrman, P. van Helden, and L. Torenvliet. P-selective self-reducible sets: A new characterization of P. In Proc. 8th STRUCTURES, pages 44\u201351. IEEE Press, 1993.","DOI":"10.1109\/SCT.1993.336542"},{"key":"8_CR8","first-page":"195","volume":"#415","author":"S. Even","year":"1980","unstructured":"S. Even and Y. Yacobi. Cryptocomplexity and NP-completeness. In Proc. 7th ICALP, pages 195\u2013207. LNCS #415, 1980.","journal-title":"LNCS"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder's toolkit. In Proc. 8th STRUCTURES, pages 120\u2013131. IEEE Press, 1993.","DOI":"10.1109\/SCT.1993.336534"},{"key":"8_CR10","first-page":"398","volume":"#665","author":"S. Fenner","year":"1993","unstructured":"S. Fenner, S. Homer, M. Ogiwara, and A. Selman. On using oracles that compute values. In Proc. 10th STACS, pages 398\u2013407. LNCS #665, 1993.","journal-title":"LNCS"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"R. Gavald\u00e0. Bounding the complexity of advice functions. In Proc. 7th STRUCTURES, pages 249\u2013254. IEEE Press, 1992.","DOI":"10.1109\/SCT.1992.215399"},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(91)90070-I","volume":"88","author":"R. Gavald\u00e0","year":"1991","unstructured":"R. Gavald\u00e0 and J. Balc\u00e1zar. Strong and robustly strong polynomial time reducibilities to sparse sets. TCS, 88:1\u201314, 1991.","journal-title":"TCS"},{"key":"8_CR13","volume-title":"Tech. Rep. TR-469","author":"L. Hemaspaandra","year":"1993","unstructured":"L. Hemaspaandra, A. Hoene, A. Naik, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Selectivity: Reductions, nondeterminism, and function classes. Tech. Rep. TR-469, U. of Rochester, Dept. of Comp. Sci., Rochester, NY, August 1993."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, A. Hoene, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Selectivity. In Proc. 5th ICCI, pages 55\u201359. IEEE Press, 1993.","DOI":"10.1109\/ICCI.1993.315404"},{"key":"8_CR15","volume-title":"Tech. Rep. 93-21","author":"E. Hemaspaandra","year":"1993","unstructured":"E. Hemaspaandra, A. Naik, M. Ogiwara, and A. Selman. P-selective sets, and reducing search to decision vs. self-reducibility. Tech. Rep. 93-21, SUNY-Buffalo, Dept. of Comp. Sci., Buffalo, NY, 1993."},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"C. Jockusch","year":"1968","unstructured":"C. Jockusch. Semirecursive sets and positive reducibility. Trans. AMS, 131:420\u2013436, 1968.","journal-title":"Trans. AMS"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th STOC, pages 302\u2013309. ACM Press, 1980.","DOI":"10.1145\/800141.804678"},{"key":"8_CR18","first-page":"209","volume":"26","author":"K. Ko","year":"1983","unstructured":"K. Ko. On self-reducibility and weak P-selectivity. JCSS, 26:209\u2013221, 1983.","journal-title":"JCSS"},{"key":"8_CR19","first-page":"28","volume":"#665","author":"J. K\u00f6bler","year":"1993","unstructured":"J. K\u00f6bler. Locating P\/poly optimally in the extended low hierarchy. In Proc. 10th STACS, pages 28\u201337. LNCS #665, 1993.","journal-title":"LNCS"},{"key":"8_CR20","first-page":"490","volume":"36","author":"M. Krentel","year":"1988","unstructured":"M. Krentel. The complexity of optimization problems. JCSS, 36:490\u2013509, 1988.","journal-title":"JCSS"},{"key":"8_CR21","volume-title":"Tech. Rep. OSU-CISRC-2\/91-TR6","author":"T. Long","year":"1991","unstructured":"T. Long and M. Sheu. A refinement of the low and high hierarchies. Tech. Rep. OSU-CISRC-2\/91-TR6, Ohio State Univ., Dept. Comp. Sci., Columbus, Ohio, February 1991."},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(93)90120-I","volume":"115","author":"L. Longpr\u00e9","year":"1993","unstructured":"L. Longpr\u00e9 and A. Selman. Hard promise problems and nonuniform complexity. TCS, 115:277\u2013290, 1993.","journal-title":"TCS"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"A. Naik, M. Ogiwara, and A. Selman. P-selective sets, and reducing search to decision vs. self-reducibility. In Proc. 8th STRUCTURES, pages 52\u201364. IEEE Press, 1993.","DOI":"10.1109\/SCT.1993.336541"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson. Hardness vs. randomness. In Proc. 29th FOCS, pages 2\u201311. IEEE Press, 1988.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"8_CR25","unstructured":"J. Royer, August 1993. Personal Comm."},{"key":"8_CR26","first-page":"14","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning. A low and a high hierarchy within NP. JCSS, 27:14\u201328, 1983.","journal-title":"JCSS"},{"key":"8_CR27","doi-asserted-by":"crossref","unstructured":"A. Selman. A taxonomy of complexity classes of functions. JCSS. In press.","DOI":"10.1016\/S0022-0000(05)80009-1"},{"key":"8_CR28","first-page":"55","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. MST, 13:55\u201365, 1979.","journal-title":"MST"},{"key":"8_CR29","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(88)90030-2","volume":"78","author":"A. Selman","year":"1988","unstructured":"A. Selman. Promise problems complete for complexity classes. Inf. and Comput., 78:87\u201398, 1988.","journal-title":"Inf. and Comput."},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1137\/0221023","volume":"21","author":"S. Toda","year":"1992","unstructured":"S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomialtime hierarchy. SIAM J. Comput., 21:316\u2013328, 1992.","journal-title":"SIAM J. Comput."},{"key":"8_CR31","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20:865\u2013877, 1991.","journal-title":"SIAM J. Comput."},{"key":"8_CR32","unstructured":"N. Vereshchagin, 1994. Personal Comm."},{"key":"8_CR33","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. TCS, 47:85\u201393, 1986.","journal-title":"TCS"},{"key":"8_CR34","first-page":"203","volume":"26","author":"O. Watanabe","year":"1993","unstructured":"O. Watanabe and S. Toda. Structural analysis of the complexity of inverse functions. MST, 26:203\u2013214, 1993.","journal-title":"MST"},{"key":"8_CR35","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C. Yap","year":"1983","unstructured":"C. Yap. Some consequences of non-uniform conditions on uniform classes. TCS, 26:287\u2013300, 1983.","journal-title":"TCS"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58325-4_166.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:13:33Z","timestamp":1619558013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58325-4_166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583257","9783540486534"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-58325-4_166","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}