{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:58:07Z","timestamp":1725551887859},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540311980"},{"type":"electronic","value":"9783540322177"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11611257_30","type":"book-chapter","created":{"date-parts":[[2006,1,5]],"date-time":"2006-01-05T16:37:18Z","timestamp":1136479038000},"page":"323-331","source":"Crossref","is-referenced-by-count":1,"title":["P-Selectivity, Immunity, and the Power of One Bit"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[]},{"given":"Leen","family":"Torenvliet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","first-page":"76","volume-title":"Proceedings of the 17th IEEE Symposium on Foundations of Computer Science","author":"L. Berman","year":"1976","unstructured":"Berman, L.: On the Structure of Complete Sets. In: Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, October 1976, pp. 76\u201380. IEEE Computer Society, Los Alamitos (1976)"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BFb0039602","volume-title":"STACS 87","author":"J. Cai","year":"1987","unstructured":"Cai, J.: Probability one Separation of the Boolean Hierarchy. In: Brandenburg, F.J., Wirsing, M., Vidal-Naquet, G. (eds.) STACS 1987. LNCS, vol.\u00a0247, pp. 148\u2013158. Springer, Heidelberg (1987)"},{"issue":"6","key":"30_CR3","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The Boolean Hierarchy I: Structural Properties. SIAM Journal on Computing\u00a017(6), 1232\u20131252 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"30_CR4","doi-asserted-by":"publisher","first-page":"1309","DOI":"10.1137\/S0097539703427550","volume":"33","author":"L. Hemaspaandra","year":"2004","unstructured":"Hemaspaandra, L., Hempel, H., Nickelsen, A.: Algebraic Properties for Selector Functions. SIAM Journal on Computing\u00a033(6), 1309\u20131337 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"30_CR5","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Watanabe, O.: The Complexity of Kings. Technical Report TR-870, Department of Computer Science, University of Rochester, Rochester, NY (June 2005)"},{"issue":"4","key":"30_CR6","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"},{"key":"30_CR7","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)"},{"key":"#cr-split#-30_CR8.1","unstructured":"Hemaspaandra, L., Ogihara, M., Zaki, M., Zimand, M.: The Complexity of Finding Top-Toda-Equivalence-Class Members MINOR PANIC: hem-ogi-zak-zim: Missing year\/issue\/voume, and remove. Theory of Computing Systems (to appear);"},{"key":"#cr-split#-30_CR8.2","unstructured":"Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.??2976, pp. 90???99. Springer, Heidelberg (2004)"},{"issue":"2","key":"30_CR9","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":"30_CR10","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":"#cr-split#-30_CR11.1","doi-asserted-by":"crossref","unstructured":"Karp, R., Lipton, R.: Some Connections between Nonuniform and Uniform Complexity Classes. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 302???309. ACM Press, New York (1980);","DOI":"10.1145\/800141.804678"},{"key":"#cr-split#-30_CR11.2","unstructured":"An extended version has also appeared as: Turing Machines that Take Advice, L???Enseignement Math??matique. 2nd series, vol.??28, pp. 191???209 (1982)"},{"issue":"2","key":"30_CR12","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K. Ko","year":"1983","unstructured":"Ko, K.: On Self-Reducibility and Weak P-Selectivity. Journal of Computer and System Sciences\u00a026(2), 209\u2013221 (1983)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"30_CR13","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"},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/3-540-45655-4_59","volume-title":"Computing and Combinatorics","author":"A. Nickelsen","year":"2002","unstructured":"Nickelsen, A., Tantau, T.: On Reachability in Graphs with Bounded Independence Number. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol.\u00a02387, pp. 554\u2013563. Springer, Heidelberg (2002)"},{"issue":"1","key":"30_CR15","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/637437.637445","volume":"34","author":"A. Nickelsen","year":"2003","unstructured":"Nickelsen, A., Tantau, T.: Partial information classes. SIGACT News\u00a034(1), 32\u201346 (2003)","journal-title":"SIGACT News"},{"key":"30_CR16","volume-title":"The Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"Rogers Jr., H.: The Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0213023","volume":"13","author":"U. Sch\u00f6ning","year":"1984","unstructured":"Sch\u00f6ning, U., Book, R.: Immunity, Relativization, and Nondeterminism. SIAM Journal on Computing\u00a013, 329\u2013337 (1984)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"30_CR18","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":"3","key":"30_CR19","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/0022-0000(81)90068-4","volume":"23","author":"A. Selman","year":"1981","unstructured":"Selman, A.: Some Observations on NP Real Numbers and P-Selective Sets. Journal of Computer and System Sciences\u00a023(3), 326\u2013332 (1981)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"30_CR20","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":"30_CR21","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"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2006: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11611257_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:09:31Z","timestamp":1619507371000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11611257_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540311980","9783540322177"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11611257_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}