{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:08:35Z","timestamp":1725574115792},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212584"},{"type":"electronic","value":"9783540246985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24698-5_13","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:28:22Z","timestamp":1294439302000},"page":"90-99","source":"Crossref","is-referenced-by-count":1,"title":["The Complexity of Finding Top-Toda-Equivalence-Class Members"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"Mitsunori","family":"Ogihara","sequence":"additional","affiliation":[]},{"given":"Mohammed J.","family":"Zaki","sequence":"additional","affiliation":[]},{"given":"Marius","family":"Zimand","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"13_CR1","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(91)90023-U","volume":"86","author":"A. Bertoni","year":"1991","unstructured":"Bertoni, A., Goldwurm, M., Sabadini, N.: The complexity of computing the number of strings of given length in context-free languages. Theoretical Computer Science\u00a086(2), 325\u2013342 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"13_CR2","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/193820.193828","volume":"25","author":"D. Denny-Brown","year":"1994","unstructured":"Denny-Brown, D., Han, Y., Hemaspaandra, L., Torenvliet, L.: Semi-membership algorithms: Some recent advances. SIGACT News\u00a025(3), 12\u201323 (1994)","journal-title":"SIGACT News"},{"issue":"3","key":"13_CR3","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/0220034","volume":"20","author":"A. Goldberg","year":"1991","unstructured":"Goldberg, A., Sipser, M.: Compression and ranking. SIAM Journal on Computing\u00a020(3), 524\u2013536 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR4","first-page":"210","volume-title":"Proceedings of the 24th IEEE Symposium on Foundations of Computer Science","author":"Y. Gurevich","year":"1983","unstructured":"Gurevich, Y.: Algebras of feasible functions. In: Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pp. 210\u2013214. IEEE Computer Society Press, Los Alamitos (1983)"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/BFb0015750","volume-title":"Automata, Languages and Programming","author":"J. Hartmanis","year":"1985","unstructured":"Hartmanis, J., Immerman, N.: On complete problems for NP\u2229coNP. In: Brauer, W. (ed.) ICALP 1985. LNCS, vol.\u00a0194, pp. 250\u2013259. Springer, Heidelberg (1985)"},{"issue":"1-2","key":"13_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"Hartmanis, J., Yesha, Y.: Computation times of NP sets of different densities. Theoretical Computer Science\u00a034(1-2), 17\u201332 (1984)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"13_CR7","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0022-0000(90)90038-M","volume":"41","author":"L. Hemachandra","year":"1990","unstructured":"Hemachandra, L., Rudich, S.: On the complexity of ranking. Journal of Computer and System Sciences\u00a041(2), 251\u2013271 (1990)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1006\/jcss.1996.0061","volume":"53","author":"E. Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, E., Naik, A., Ogihara, M., Selman, A.: P-selective sets and reducing search to decision vs. self-reducibility. Journal of Computer and System Sciences\u00a053(2), 194\u2013209 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/3-540-44679-6_6","volume-title":"Computing and Combinatorics","author":"L. Hemaspaandra","year":"2001","unstructured":"Hemaspaandra, L., Hempel, H., Nickelsen, A.: Algebraic properties for deterministic selectivity. In: Wang, J. (ed.) COCOON 2001. LNCS, vol.\u00a02108, pp. 49\u201358. Springer, Heidelberg (2001)"},{"key":"13_CR10","unstructured":"Hemaspaandra, L., Hempel, H., Nickelsen, A.: Algebraic properties for deterministic and nondeterministic selectivity. Technical Report TR-778, Department of Computer Science, University of Rochester, Rochester, NY (May 2002) (revised, May 2003)"},{"issue":"4","key":"13_CR11","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1142\/S0129054195000214","volume":"6","author":"L. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L., Hoene, A., Naik, A., Ogiwara, M., Selman, A., Thierauf, T., Wang, J.: Nondeterministically selective sets. International Journal of Foundations of Computer Science\u00a06(4), 403\u2013416 (1995)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"4","key":"13_CR12","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539794268315","volume":"25","author":"L. Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, L., Naik, A., Ogihara, M., Selman, A.: Computing solutions uniquely collapses the polynomial hierarchy. SIAM Journal on Computing\u00a025(4), 697\u2013708 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"13_CR13","first-page":"670","volume":"4","author":"L. Hemaspaandra","year":"1998","unstructured":"Hemaspaandra, L., Nasipak, C., Parkins, K.: A note on linear-nondeterminism, linearsized, Karp\u2013Lipton advice for the P-selective sets. Journal of Universal Computer Science\u00a04(8), 670\u2013674 (1998)","journal-title":"Journal of Universal Computer Science"},{"key":"13_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04880-1","volume-title":"The Complexity Theory Companion","author":"L. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L., Ogihara, M.: The Complexity Theory Companion. Springer, Heidelberg (2002)"},{"issue":"2","key":"13_CR15","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1006\/jcss.2001.1815","volume":"64","author":"L. Hemaspaandra","year":"2002","unstructured":"Hemaspaandra, L., Ogihara, M., Wechsung, G.: Reducing the number of solutions of NP functions. Journal of Computer and System Sciences\u00a064(2), 311\u2013328 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L., Ogihara, M., Zaki, M., Zimand, M.: The complexity of finding top-Todaequivalence-class members. Technical Report TR-808, Department of Computer Science, University of Rochester, Rochester, NY (August 2003)","DOI":"10.1007\/978-3-540-24698-5_13"},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0304-3975(95)00076-3","volume":"154","author":"L. Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, L., Torenvliet, L.: Optimal advice. Theoretical Computer Science\u00a0154(2), 367\u2013377 (1996)","journal-title":"Theoretical Computer Science"},{"key":"13_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05080-4","volume-title":"Theory of Semi-Feasible Algorithms","author":"L. Hemaspaandra","year":"2003","unstructured":"Hemaspaandra, L., Torenvliet, L.: Theory of Semi-Feasible Algorithms. Springer, Heidelberg (2003)"},{"key":"13_CR19","unstructured":"Hemaspaandra, L., Zaki, M., Zimand, M.: Polynomial-time semi-rankable sets. Journal of Computing and Information\u00a02(1); Special Issue: Proceedings of the 8th International Conference on Computing and Information, pp.\u00a050\u201367 (1996) CD-ROM ISSN 1201- 8511\/V2\/#1"},{"issue":"1","key":"13_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02090763","volume":"23","author":"D. Huynh","year":"1990","unstructured":"Huynh, D.: The complexity of ranking simple languages. Mathematical Systems Theory\u00a023(1), 1\u201320 (1990)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"13_CR21","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"C. Jockusch","year":"1968","unstructured":"Jockusch, C.: Semirecursive sets and positive reducibility. Transactions of the AMS\u00a0131(2), 420\u2013436 (1968)","journal-title":"Transactions of the AMS"},{"issue":"2","key":"13_CR22","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02476378","volume":"15","author":"H. Landau","year":"1953","unstructured":"Landau, H.: On dominance relations and the structure of animal societies, III: The condition for score structure. Bulletin of Mathematical Biophysics\u00a015(2), 143\u2013148 (1953)","journal-title":"Bulletin of Mathematical Biophysics"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(98)00060-7","volume":"207","author":"A. Naik","year":"1998","unstructured":"Naik, A., Rogers, J., Royer, J., Selman, A.: A hierarchy based on output multiplicity. Theoretical Computer Science\u00a0207(1), 131\u2013157 (1998)","journal-title":"Theoretical Computer Science"},{"key":"#cr-split#-13_CR24.1","unstructured":"Nickelsen, A.: Polynomial-time partial information classes. Wissenschaft und TechnikVerlag (2001);"},{"key":"#cr-split#-13_CR24.2","unstructured":"Also Ph.D. thesis, Technische Universit\u00e4t Berlin, Berlin, Germany (1999)"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Nickelsen, A., Tantau, T.: Partial information classes. SIGACT News\u00a034(1) (2003)","DOI":"10.1145\/637437.637445"},{"issue":"1","key":"13_CR26","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(96)00030-0","volume":"58","author":"M. Ogihara","year":"1996","unstructured":"Ogihara, M.: Functions computable with limited access to NP. Information Processing Letters\u00a058(1), 35\u201338 (1996)","journal-title":"Information Processing Letters"},{"issue":"1","key":"13_CR27","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"Selman, A.: P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory\u00a013(1), 55\u201365 (1979)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"13_CR28","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/S0019-9958(82)80084-3","volume":"52","author":"A. Selman","year":"1982","unstructured":"Selman, A.: Analogues of semirecursive sets and effective reducibilities to the study of NP complexity. Information and Control\u00a052(1), 36\u201351 (1982)","journal-title":"Information and Control"},{"issue":"3","key":"13_CR29","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(82)90039-1","volume":"19","author":"A. Selman","year":"1982","unstructured":"Selman, A.: Reductions on NP and P-selective sets. Theoretical Computer Science\u00a019(3), 287\u2013304 (1982)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"13_CR30","doi-asserted-by":"publisher","first-page":"1201","DOI":"10.1137\/S0097539702410053","volume":"32","author":"J. Shen","year":"2003","unstructured":"Shen, J., Sheng, L., Wu, J.: Searching for sorted sequences in tournaments. SIAM Journal on Computing\u00a032(5), 1201\u20131209 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/BFb0012797","volume-title":"Automata, Languages, and Programming","author":"M. Sipser","year":"1982","unstructured":"Sipser, M.: On relativization and the existence of complete sets. In: Nielsen, M., Schmidt, E.M. (eds.) ICALP 1982. LNCS, vol.\u00a0140, pp. 523\u2013531. Springer, Heidelberg (1982)"},{"key":"13_CR32","unstructured":"Tantau, T.: A note on the complexity of the reachability problem for tournaments. Technical Report TR01-092, Electronic Colloquium on Computational Complexity (November 2001), http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"issue":"2","key":"13_CR33","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF02090391","volume":"24","author":"S. Toda","year":"1991","unstructured":"Toda, S.: On polynomial-time truth-table reducibilities of intractable sets to P-selective sets. Mathematical Systems Theory\u00a024(2), 69\u201382 (1991)","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","LATIN 2004: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24698-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T02:56:17Z","timestamp":1637117777000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24698-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212584","9783540246985"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24698-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}