{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:07Z","timestamp":1742596807228,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571636"},{"type":"electronic","value":"9783540479239"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993]]},"DOI":"10.1007\/3-540-57163-9_24","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:07:42Z","timestamp":1330258062000},"page":"289-298","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Easily checked self-reducibility"],"prefix":"10.1007","author":[{"given":"Lane A.","family":"Hemachandra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"24_CR1","unstructured":"V. Arvind and S. Biswas. Kernel constructible languages. In Record of the 3rd Conference on Foundations of Software Technology and Theoretical Computer Science, pages 520\u2013538. National Centre for Software Development and Computing Technique, Tata Institute of Fundamental Research, Dec. 1983."},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(89)90125-4","volume":"68","author":"V. Arvind","year":"1989","unstructured":"V. Arvind and S. Biswas. On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas. Theoretical Computer Science, 68(1):1\u201314, 1989.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"24_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 6(2):305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"24_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95\u2013111, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz. An oracle relative to which the isomorphism conjecture holds. In Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pages 30\u201339. IEEE Computer Society Press, Oct. 1992.","DOI":"10.1109\/SFCS.1992.267821"},{"issue":"3","key":"24_CR6","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0208034","volume":"8","author":"S. Fortune","year":"1979","unstructured":"S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, 8(3):431\u2013433, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"24_CR7","unstructured":"R. Gavald\u00e1, L. Torenvliet, O. Watanabe, and J. Balc\u00e1zar. Generalized Kolmogorov complexity in relativized separations. In Proceedings of the 15th Symposium on Mathematical Foundations of Computer Science, pages 266\u2013276. Springer-Verlag Lecture Notes in Computer Science #452, Aug. 1990."},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"F. Harary. A survey of the reconstruction conjecture. In Graphs and Combinatorics, pages 18\u201328. Springer-Verlag Lecture Notes in Mathematics #406, 1974.","DOI":"10.1007\/BFb0066431"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 439\u2013445. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"24_CR10","volume-title":"Technical Report TR-347","author":"L. Hemachandra","year":"1990","unstructured":"L. Hemachandra, M. Ogiwara, and S. Toda. Space-efficient recognition of sparse selfreducible languages. Technical Report TR-347, University of Rochester, Department of Computer Science, Rochester, NY, May 1990."},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, M. Ogiwara, and O. Watanabe. How hard are sparse sets? In Proceedings of the 7th Structure in Complexity Theory Conference, pages 222\u2014238. IEEE Computer Society Press, June 1992.","DOI":"10.1109\/SCT.1992.215396"},{"issue":"2","key":"24_CR12","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90144-1","volume":"47","author":"S. Homer","year":"1986","unstructured":"S. Homer. On simple and creative sets in NP. Theoretical Computer Science, 47(2):169\u2013180, 1986.","journal-title":"Theoretical Computer Science"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"J. Hopcroft. Recent directions in algorithmic research. In Proceedings 5th GI Conference on Theoretical Computer Science, pages 123\u2013134. Springer-Verlag Lecture Notes in Computer Science #104, 1981.","DOI":"10.1007\/BFb0017304"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"D. Joseph and P. Young. Self-reducibility: Effects of internal structure on computational complexity. In A. Selman, editor, Complexity Theory Retrospective, pages 82\u2013107. Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-4478-3_6"},{"issue":"5","key":"24_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(90)90191-Y","volume":"33","author":"J. K\u00e4mper","year":"1990","unstructured":"J. K\u00e4mper. A result relating disjunctive self-reducibility to P-immunity. Information Processing Letters, 33(5):239\u2013242, 1990.","journal-title":"Information Processing Letters"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 302\u2013309, Apr. 1980.","DOI":"10.1145\/800141.804678"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(91)90190-D","volume":"81","author":"S. Khadilkar","year":"1991","unstructured":"S. Khadilkar and S. Biswas. Padding, commitment and self-reducibility. Theoretical Computer Science, 81:189\u2013199, 1991.","journal-title":"Theoretical Computer Science"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"D. Kratsch and L. Hemachandra. On the complexity of graph reconstruction. In Proceedings of the 8th Conference on Fundamentals of Computation Theory, pages 318\u2013328. Springer-Verlag Lecture Notes in Computer Science #529, Sept. 1991. To appear in Mathematical Systems Theory.","DOI":"10.1007\/3-540-54458-5_76"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vitanyi. Applications of Kolmogorov complexity in the theory of computation. In A. Selman, editor, Complexity Theory Retrospective, pages 147\u2013203. Springer-Verlag, 1990.","DOI":"10.1007\/978-1-4612-4478-3_8"},{"issue":"2","key":"24_CR20","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25(2):130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0304-3975(85)90139-2","volume":"39","author":"S. Mahaney","year":"1985","unstructured":"S. Mahaney and P. oung. Reductions among polynomial isomorphism types. Theoretical Computer Science, 39:207\u2013224, 1985.","journal-title":"Theoretical Computer Science"},{"key":"24_CR22","unstructured":"M. Ogiwara and A. Lozano. On one-query self-reducible sets. Theoretical Computer Science. To appear. Preliminary version appears in Proceedings of the 6th Structure in Complexity Theory Conference (1991), IEEE Computer Society Press, pp. 139\u2013151."},{"issue":"3","key":"24_CR23","doi-asserted-by":"publisher","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, June 1991.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"24_CR24","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1137\/0212038","volume":"12","author":"E. Ukkonen","year":"1983","unstructured":"E. Ukkonen. Two results on polynomial time truth-table reductions to sparse sets. SIAM Journal on Computing, 12(3):580\u2013587, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"24_CR25","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant. The relative complexity of checking and evaluating. Information Processing Letters, 5:20\u201323, 1976.","journal-title":"Information Processing Letters"},{"issue":"3","key":"24_CR26","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0212027","volume":"12","author":"Y. Yesha","year":"1983","unstructured":"Y. Yesha. On certain polynomial-time truth-table reducibilities of complete sets to sparse sets. SIAM Journal on Computing, 12(3):411\u2013425, 1983.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57163-9_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:00:30Z","timestamp":1742594430000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57163-9_24"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571636","9783540479239"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-57163-9_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"30 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}