{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:26:47Z","timestamp":1787509607541,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"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":[[1986]]},"DOI":"10.1007\/3-540-16486-3_85","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:45:23Z","timestamp":1330177523000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["The complexity of sparse sets in P"],"prefix":"10.1007","author":[{"given":"Eric W.","family":"Allender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"1_CR1","unstructured":"E. W. Allender, Invertible functions, Doctoral Dissertation, Georgia Institute of Technology."},{"key":"1_CR2","unstructured":"E. W. Allender, Characterizations of PUNC and precomputation, to be presented at the 13th International Colloquium on Automata, Languages and Programming, and will appear in Lecture Notes in Computer Science."},{"key":"1_CR3","unstructured":"E. W. Allender, Isomorphisms and 1L reductions, These Proceedings."},{"key":"1_CR4","unstructured":"J. L. Balcazar and R. V. Book, Sets with small generalized Kolmogorov complexity, Technical Report MSRI 00918-86, Mathematical Sciences Research Institute, Berkeley."},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"J. L. Balcazar, J. Diaz, J. Gabarro, On some \u201cnon-uniform\u201d complexity measures, 5th Conference on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 199, pp. 18\u201327.","DOI":"10.1007\/BFb0028787"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"P. W. Beame, S. A. Cook, and H. J. Hoover, Log depth circuits for division and related problems, Proc. 25th IEEE Symposium on Foundations of Computer Science, pp. 1\u201311.","DOI":"10.1109\/SFCS.1984.715894"},{"key":"1_CR7","unstructured":"L. Berman, Polynomial reducibilities and complete sets, Doctoral Dissertation, Cornell University."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"R. V. Book, Tally languages and complexity classes, Information and Control 26, 186\u2013193.","DOI":"10.1016\/S0019-9958(74)90473-2"},{"key":"1_CR9","unstructured":"F.-J. Brandenburg, On one-way auxiliary pushdown automata, Proc. 3rd GI Conference, Lecture Notes in Computer Science 48, pp. 133\u2013144."},{"key":"1_CR10","unstructured":"F.-J. Brandenburg, The contextsensitivity of contextsensitive grammars and languages, Proc. 4th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 52, pp. 272\u2013281."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"M. P. Chytil, Comparison of the active visiting and the crossing complexities, Proc. 6th Conference on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 53, pp. 272\u2013281.","DOI":"10.1007\/3-540-08353-7_145"},{"key":"1_CR12","unstructured":"S. A. Cook, Characterizations of pushdown machines in terms of time-bounded computers, J. ACM 19, 175\u2013183."},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen, Parallel powering, Proc. 25th Annual ACM Symposium on Theory of Computing, pp. 31\u201336.","DOI":"10.1109\/SFCS.1984.715898"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and M. Sipser, Compression and ranking, Proc. 17th Annual ACM Symposium on Theory of Computing, pp. 440\u2013448.","DOI":"10.1145\/22145.22194"},{"key":"1_CR15","unstructured":"J. Grollmann, Complexity measures for public-key cryptosystems, Doctoral Dissertation, Dortmund."},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"J. Grollmann and A. Selman, Complexity measures for public-key cryptosystems, Proc. 25th IEEE Symposium on Foundations of Computer Science, pp. 495\u2013503.","DOI":"10.1109\/SFCS.1984.715952"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, On sparse sets in NP = P, Information Processing Letters 16, 55\u201360.","DOI":"10.1016\/0020-0190(83)90024-8"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, V. Sewelson, and N. Immerman, Sparse sets in NP-P: EXPTIME versus NEXPTIME, Proc. 15th Annual ACM Symposium on Theory of Computing, pp. 382\u2013391.","DOI":"10.1145\/800061.808769"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"J. Hartmanis and Y. Yesha, Computation times of NP sets of different densities, Theoretical Computer Science 34, 17\u201332.","DOI":"10.1016\/0304-3975(84)90111-7"},{"key":"1_CR21","unstructured":"J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass."},{"key":"1_CR22","unstructured":"D. T. Huynh, Non-uniform complexity and the randomness of certain complete languages, Technical Report TR 85-34, Computer Science Department, Iowa State University."},{"key":"1_CR23","unstructured":"D. T. Huynh, Resource-bounded Kolmogorov complexity of hard languages, These Proceedings."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"K.-I. Ko, On the definition of some complexity classes of real numbers, Mathematical Systems Theory 16, 95\u2013109.","DOI":"10.1007\/BF01744572"},{"key":"1_CR25","unstructured":"K.-I. Ko, A definition of infinite pseudorandom sequences, manuscript, University of Houston."},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"N. Pippenger, Pebbling with an auxiliary pushdown, J. Computer and System Sciences 23, 151\u2013165.","DOI":"10.1016\/0022-0000(81)90011-8"},{"key":"1_CR27","unstructured":"R. Rubinstein, Generalized Kolmogorov complexity, tally sets, sparseness, etc. \u2014 a few notes, manuscript, Iowa State University."},{"key":"1_CR28","doi-asserted-by":"crossref","unstructured":"W. L. Ruzzo, On uniform circuit complexity, J. Computer and System Sciences 21, 365\u2013383.","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"1_CR29","unstructured":"W. L. Ruzzo, personal communication."},{"key":"1_CR30","unstructured":"V. Sewelson, A study of the structure of NP, Doctoral Dissertation, Cornell University."},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"L. Valiant, Relative complexity of checking and evaluating, Information Processing Letters 5, 20\u201323.","DOI":"10.1016\/0020-0190(76)90097-1"},{"key":"1_CR32","unstructured":"G. Wechsung, A note on the return complexity, Elektronische Informationsverarbeitung und Kybernetik 16, 139\u2013146."},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"G. Wechsung and A. Brandstadt, A relation between space, return and dual return complexities, Theoretical Computer Science 9, 127\u2013140.","DOI":"10.1016\/0304-3975(79)90010-0"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_85","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T16:27:30Z","timestamp":1742574450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_85"}},"subtitle":["Preliminary report"],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_85","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}