{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:55Z","timestamp":1725663775477},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578116"},{"type":"electronic","value":"9783540483373"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[[1994]]},"DOI":"10.1007\/3-540-57811-0_17","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:24:33Z","timestamp":1330244673000},"page":"203-212","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On self-reducible sets of low information content"],"prefix":"10.1007","author":[{"given":"Martin","family":"Mundhenk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"V. Arvind, Y. Han, L. Hemachandra, J. K\u00f6bler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Sch\u00f6ning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. In Complexity Theory, K. Ambos-Spies, S. Homer, and U. Sch\u00f6ning (eds.). Cambridge University Press, 1993.","DOI":"10.1007\/3-540-55719-9_72"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"V. Arvind, J. K\u00f6bler, and M. Mundhenk. Lowness and the complexity of sparse and tally descriptions. Proc. 3rd ISAAC, Lecture Notes in Computer Science, #650:249\u2013258, Springer Verlag, 1992.","DOI":"10.1007\/3-540-56279-6_78"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"V. Arvind, J. K\u00f6bler, and M. Mundhenk. Hausdorff reductions to sparse sets and to sets of high information content. Proc. 18th MFCS, Lecture Notes in Computer Science, #711:232\u2013241, Springer Verlag, 1993.","DOI":"10.1007\/3-540-57182-5_15"},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0022-0000(90)90025-G","volume":"41","author":"J. Balc\u00e1zar","year":"1990","unstructured":"J. Balc\u00e1zar. Self-reducibility. Journal of Computer and System Sciences, 41:367\u2013388, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR5","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1137\/0215053","volume":"15","author":"J. L. Balc\u00e1zar","year":"1986","unstructured":"J.L. Balc\u00e1zar, R. Book, and U. Sch\u00f6ming. Sparse sets, lowness and highness. SIAM Journal on Computing, 15:739\u2013747, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"J.L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. EATCS Monographs on Theoretical Computer Science, Springer Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"P. Berman. Relationship between density and deterministic complexity of NP-complete languages. Proceedings of the 5th ICALP, Lecture Notes in Computer Science, #62:63\u201371, Springer Verlag, 1978.","DOI":"10.1007\/3-540-08860-1_6"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1137\/0222029","volume":"22","author":"R. Book","year":"1993","unstructured":"R. Book and J. Lutz. On languages with very high space-bounded Kolmogorov complexity. SIAM Journal on Computing, 22:395\u2013402, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR9","unstructured":"H. Buhrman, L. Longpr\u00e9, and E. Spaan. Sparse reduces conjunctively to tally. Proceedings of the 8th Structure in Complexity Theory Conference, IEEE Computer Society Press, 1993."},{"issue":"3","key":"17_CR10","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","volume":"39","author":"J. Kadin","year":"1989","unstructured":"J. Kadin. pNP[log n] and sparse Turing-complete sets for NP. Journal of Computer and System Sciences, 39(3):282\u2013298, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. Proceedings of the 12th ACM Symposium on Theory of Computing, 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K. Ko","year":"1983","unstructured":"K. Ko. On self-reducibility and weak p-selectivity. Journal of Computer and System Sciences, 26:209\u2013221, 1983.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"17_CR13","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/0890-5401(89)90029-1","volume":"81","author":"K. Ko","year":"1989","unstructured":"K. Ko. Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Information and Computation, 81(1):62\u201387, 1989.","journal-title":"Information and Computation"},{"key":"17_CR14","unstructured":"K. Ko, P. Orponen, U. Sch\u00f6ming, and O. Watanabe. Instance complexity. Journal of the ACM, to appear."},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler. Locating P\/poly optimally in the extended low hierarchy. Proc. of the 10th STACS, Lecture Notes in Computer Science, #665:28\u201337, Springer Verlag, 1993.","DOI":"10.1007\/3-540-56503-5_5"},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02090392","volume":"24","author":"A. Lozano","year":"1991","unstructured":"A. Lozano and J. Tor\u00e1n. Self-reducible sets of small density. Mathematical Systems Theory, 24:83\u2013100, 1991.","journal-title":"Mathematical Systems Theory"},{"key":"17_CR17","volume-title":"Tech. Report MIT\/LCS\/TM-126","author":"A. Meyer","year":"1979","unstructured":"A. Meyer, M. Paterson. With what frequency are apparently intractable problems difficult? Tech. Report MIT\/LCS\/TM-126, Lab. for Computer Science, MIT, Cambridge, 1979."},{"issue":"3","key":"17_CR18","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471\u2013483, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR19","doi-asserted-by":"crossref","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"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. Complexity and Structure, Lecture Notes in Computer Science, #211, Springer Verlag, 1985","DOI":"10.1007\/3-540-16079-5"},{"key":"17_CR21","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. W. Wagner","year":"1987","unstructured":"K.W. Wagner. More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science, 51:53\u201380, 1987.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57811-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T19:02:32Z","timestamp":1578510152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57811-0_17"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578116","9783540483373"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-57811-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}