{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:23:37Z","timestamp":1775589817702,"version":"3.50.1"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030416713","type":"print"},{"value":"9783030416720","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-41672-0_3","type":"book-chapter","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T07:03:04Z","timestamp":1582182184000},"page":"19-47","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Power of Self-Reducibility: Selectivity, Information, and Approximation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0659-5204","authenticated-orcid":false,"given":"Lane A.","family":"Hemaspaandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"key":"3_CR1","first-page":"1","volume-title":"Complexity Theory","author":"V Arvind","year":"1993","unstructured":"Arvind, V., Han, Y., Hemachandra, L., K\u00f6bler, J., Lozano, A., Mundhenk, M., Ogiwara, M., Sch\u00f6ning, U., Silvestri, R., Thierauf, T.: Reductions to sets of low information content. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory, pp. 1\u201345. Cambridge University Press, Cambridge (1993)"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/3-540-08860-1_6","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"1978","unstructured":"Berman, P.: Relationship between density and deterministic complexity of NP-complete languages. In: Ausiello, G., B\u00f6hm, C. (eds.) ICALP 1978. LNCS, vol. 62, pp. 63\u201371. Springer, Heidelberg (1978). https:\/\/doi.org\/10.1007\/3-540-08860-1_6"},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/0890-5401(89)90063-1","volume":"82","author":"J-Y Cai","year":"1989","unstructured":"Cai, J.-Y., Hemachandra, L.: Enumerative counting is hard. Inf. Comput. 82(1), 34\u201344 (1989)","journal-title":"Inf. Comput."},{"issue":"4","key":"3_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(91)90103-O","volume":"38","author":"J-Y Cai","year":"1991","unstructured":"Cai, J.-Y., Hemachandra, L.: A note on enumerative counting. Inf. Process. Lett. 38(4), 215\u2013219 (1991)","journal-title":"Inf. Process. Lett."},{"key":"3_CR5","unstructured":"Clay Mathematics Institute: Millennium problems (web page) (2019). https:\/\/www.claymath.org\/millennium-problems . Accessed 10 July 2019"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM Press, May 1971","DOI":"10.1145\/800157.805047"},{"issue":"3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0208034","volume":"8","author":"S Fortune","year":"1979","unstructured":"Fortune, S.: A note on sparse complete sets. SIAM J. Comput. 8(3), 431\u2013433 (1979)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR8","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/3319627.3319636","volume":"50","author":"W Gasarch","year":"2019","unstructured":"Gasarch, W.: The third P =? NP poll. SIGACT News 50(1), 38\u201359 (2019)","journal-title":"SIGACT News"},{"key":"3_CR9","unstructured":"Gla\u00dfer, C.: Consequences of the existence of sparse sets hard for NP under a subclass of truth-table reductions. Technical report, TR 245, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, Germany, January 2000"},{"issue":"4","key":"3_CR10","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/369836.369838","volume":"31","author":"C Gla\u00dfer","year":"2000","unstructured":"Gla\u00dfer, C., Hemaspaandra, L.: A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions. SIGACT News 31(4), 39\u201351 (2000)","journal-title":"SIGACT News"},{"key":"3_CR11","unstructured":"Hemachandra, L., Ogiwara, M., Watanabe, O.: How hard are sparse sets? In: Proceedings of the 7th Structure in Complexity Theory Conference, pp. 222\u2013238. IEEE Computer Society Press, June 1992"},{"key":"3_CR12","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Menton, C.: Search versus decision for election manipulation problems. In: Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science, vol. 20, pp. 377\u2013388. Leibniz International Proceedings in Informatics (LIPIcs), February\/March 2013"},{"key":"3_CR13","unstructured":"Hemaspaandra, L.: The power of self-reducibility: selectivity, information, and approximation (2019). File set\u2013providing slides and their source code. http:\/\/www.cs.rochester.edu\/u\/lane\/=self-reducibility\/ . Accessed 10 July 2019"},{"issue":"1\u20133","key":"3_CR14","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/S0304-3975(02)00576-5","volume":"302","author":"L Hemaspaandra","year":"2003","unstructured":"Hemaspaandra, L., Hempel, H.: P-immune sets with holes lack self-reducibility properties. Theoret. Comput. Sci. 302(1\u20133), 457\u2013466 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0129054197000070","volume":"8","author":"L Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, L., Jiang, Z.: Logspace reducibility: models and equivalences. Int. J. Found. Comput. Sci. 8(1), 95\u2013108 (1997)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L., Narv\u00e1ez, D.: The opacity of backbones. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 3900\u20133906. AAAI Press, February 2017","DOI":"10.1609\/aaai.v31i1.11134"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-030-10801-4_20","volume-title":"SOFSEM 2019: Theory and Practice of Computer Science","author":"LA Hemaspaandra","year":"2019","unstructured":"Hemaspaandra, L.A., Narv\u00e1ez, D.E.: Existence versus exploitation: the opacity of backdoors and backbones under a weak assumption. In: Catania, B., Kr\u00e1lovi\u010d, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 247\u2013259. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10801-4_20"},{"key":"3_CR18","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/978-3-662-04880-1"},{"issue":"3","key":"3_CR19","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/BF01206639","volume":"4","author":"L Hemaspaandra","year":"1994","unstructured":"Hemaspaandra, L., Ogihara, M., Toda, S.: Space-efficient recognition of sparse self-reducible languages. Comput. Complex. 4(3), 262\u2013296 (1994)","journal-title":"Comput. Complex."},{"issue":"4","key":"3_CR20","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1137\/S0097539792234901","volume":"24","author":"L Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L., Silvestri, R.: Easily checked generalized self-reducibility. SIAM J. Comput. 24(4), 840\u2013858 (1995)","journal-title":"SIAM J. Comput."},{"key":"3_CR21","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/978-3-662-05080-4"},{"issue":"5","key":"3_CR22","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01184814","volume":"29","author":"L Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, L., Zimand, M.: Strong self-reducibility precludes strong immunity. Math. Syst. Theory 29(5), 535\u2013548 (1996)","journal-title":"Math. Syst. Theory"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R Karp","year":"1972","unstructured":"Karp, R.: Reducibilities among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"3_CR24","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0022-0000(82)90053-8","volume":"24","author":"K Ko","year":"1982","unstructured":"Ko, K.: The maximum value problem and NP real numbers. J. Comput. Syst. Sci. 24(1), 15\u201335 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"3_CR25","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. J. Comput. Syst. Sci. 26(2), 209\u2013221 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"3_CR26","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0304-3975(87)90078-8","volume":"52","author":"K Ko","year":"1987","unstructured":"Ko, K.: On helping by robust oracle machines. Theoret. Comput. Sci. 52(1\u20132), 15\u201336 (1987)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"3_CR27","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/0210061","volume":"10","author":"K Ko","year":"1981","unstructured":"Ko, K., Moore, D.: Completeness, approximation, and density. SIAM J. Comput. 10(4), 787\u2013796 (1981)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"3_CR28","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M Krentel","year":"1988","unstructured":"Krentel, M.: The complexity of optimization problems. J. Comput. Syst. Sci. 36(3), 490\u2013509 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"3_CR29","first-page":"265","volume":"9","author":"L Levin","year":"1975","unstructured":"Levin, L.: Universal sequential search problems. Probl. Inf. Transm. 9(3), 265\u2013266 (1975)","journal-title":"Probl. Inf. Transm."},{"issue":"2","key":"3_CR30","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S Mahaney","year":"1982","unstructured":"Mahaney, S.: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. J. Comput. Syst. Sci. 25(2), 130\u2013143 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR31","first-page":"63","volume-title":"Studies in Complexity Theory","author":"S Mahaney","year":"1986","unstructured":"Mahaney, S.: Sparse sets and reducibilities. In: Book, R. (ed.) Studies in Complexity Theory, pp. 63\u2013118. Wiley, Hoboken (1986)"},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Mahaney, S.: The Isomorphism Conjecture and sparse sets. In: Hartmanis, J. (ed.) Computational Complexity Theory, pp. 18\u201346. American Mathematical Society (1989). Proceedings of Symposia in Applied Mathematics #38","DOI":"10.1090\/psapm\/038\/1020808"},{"key":"3_CR33","unstructured":"Meyer, A., Paterson, M.: With what frequency are apparently intractable problems difficult? Technical report, MIT\/LCS\/TM-126, Laboratory for Computer Science, MIT, Cambridge, MA (1979)"},{"key":"3_CR34","unstructured":"Schnorr, C.: Optimal algorithms for self-reducible problems. In: Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming, pp. 322\u2013337. Edinburgh University Press, July 1976"},{"issue":"1","key":"3_CR35","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. Math. Syst. Theory 13(1), 55\u201365 (1979)","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"3_CR36","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. J. Comput. Syst. Sci. 23(3), 326\u2013332 (1981)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3_CR37","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. Inf. Control 52(1), 36\u201351 (1982)","journal-title":"Inf. Control"},{"issue":"3","key":"3_CR38","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. Theoret. Comput. Sci. 19(3), 287\u2013304 (1982). https:\/\/doi.org\/10.1016\/0304-3975(82)90039-1","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3_CR39","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"3_CR40","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"3_CR41","unstructured":"Young, P.: How reductions to sparse sets collapse the polynomial-time hierarchy: a primer. SIGACT News 23 (1992). Part I (#3, pp. 107\u2013117), Part II (#4, pp. 83\u201394), and Corrigendum to Part I (#4, p. 94)"}],"container-title":["Lecture Notes in Computer Science","Complexity and Approximation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41672-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T02:28:31Z","timestamp":1665887311000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41672-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030416713","9783030416720"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41672-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}