{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:17Z","timestamp":1725664457227},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:04Z","timestamp":1330290244000},"page":"11-24","source":"Crossref","is-referenced-by-count":5,"title":["Compressibility and resource bounded measure"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Luc","family":"Longpr\u00e9","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender and M. Strauss. Measure on small complexity classes, with applications for BPP. In Proc. 35th IEEE Symposium on Foundations of Computer Science, pages 807\u2013818. IEEE Computer Society Press, 1994.","DOI":"10.1109\/SFCS.1994.365713"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. p-mitotic sets. In Logic and Machines, Lecture Notes in Computer Science, volume 177, pages 1\u201323. Springer-Verlag, 1994.","DOI":"10.1007\/3-540-13331-3_30"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, C. Neis, and S. A. Terwijn. Genericity and measure for exponential time. In Proceedings of the 19th Symposium on Mathematical Foundations of Computer Science, pages 221\u2013232. Springer-Verlag, 1994. To appear in Theoretical Computer Science.","DOI":"10.1007\/3-540-58338-6_69"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, S.A. Terwijn, and X. Zheng. Genericity and measure for exponential time. In Proc. ISAAC94, Lecture Notes in Computer Science, volume 834, pages 369\u2013377. Springer-Verlag, 1994. To appear in Theoretical Computer Science.","DOI":"10.1007\/3-540-58338-6_69"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett and J. Gill. Relative to a random oracle A, PA\u2260NPA\u2260 Co-NPA with probability 1. SIAM J. Comput., 10(1):96\u2013113, February 1981.","journal-title":"SIAM J. Comput."},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/3-540-59042-0_109","volume-title":"STACS 95","author":"H. Buhrman","year":"1995","unstructured":"H. Buhrman and M. Hermo. On the sparse set conjecture for sets with low density. In Ernst W. Mayr and Claude Puech, editors, STACS 95, volume 900 of Lecture Notes in Computer Science, pages 609\u2013618, Berlin, 1995. Springer-Verlag."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"H. Buhrman, P. van Helden, and L. Torenvliet. P-selective self-reducible sets: A new characterization of P. In Proc. Structure in Complexity Theory eighth annual conference, pages 44\u201351. IEEE Computer Society Press, 1993.","DOI":"10.1109\/SCT.1993.336542"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1137\/S0097539792238133","volume":"24","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24:279\u2013295, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(95)80016-6","volume":"143","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes and J. H. Lutz. Weak compleness in E and E 2. Theoretical Computer Science, 143:149\u2013158, 1995.","journal-title":"Theoretical Computer Science"},{"key":"2_CR10","first-page":"1413","volume":"14","author":"L. Levin","year":"1973","unstructured":"L. Levin. On the notion of a random sequence. Soviet Math. Dokl., 14:1413\u20131416, 1973.","journal-title":"Soviet Math. Dokl."},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"J. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. In STACS 1994, Lectures Notes in Computer Science, pages 415\u2013426. Springer-Verlag, 1994.","DOI":"10.1007\/3-540-57785-8_159"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J. Lutz","year":"1994","unstructured":"J. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, 23:762\u2013779, 1994.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"2_CR13","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J. Lutz","year":"1990","unstructured":"J. Lutz. Category and measure in complexity classes. Siam J. Computing, 19(6):1100\u20131131, December 1990.","journal-title":"Siam J. Computing"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. Lutz","year":"1992","unstructured":"J. Lutz. Almost everywhere high nonuniform complexity. J. Computer and System Sciences, 44:220\u2013258, 1992.","journal-title":"J. Computer and System Sciences"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"J. Lutz. Weakly hard problems. In Proc. Structure in Complexity Theory ninth annual conference, pages 146\u2013161. IEEE Computer Society Press, 1994. To appear in SIAM J. on Computing.","DOI":"10.1109\/SCT.1994.315808"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"M. Li and Paul Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and its Applications. Texts and Monographs in Computer Science. Springer-Verlag, 1993.","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/0304-3975(94)00023-C","volume":"136","author":"E. Mayordomo","year":"1994","unstructured":"E. Mayordomo. Almost every set in exponential time is p-bi-immune. Theoretical Computer Science, 136:487\u2013506, 1994.","journal-title":"Theoretical Computer Science"},{"key":"2_CR18","unstructured":"E. Mayordomo. Contributions to the Study of Resource-Bounded Measure. PhD thesis, Universitat Polit\u00e8cnica de Catalunya, 1994."},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"P. Martin-L\u00f6f. The definition of random sequences. Information and Control, 9:602\u2013619, 1966.","journal-title":"Information and Control"},{"key":"2_CR20","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. Schnorr","year":"1973","unstructured":"C. Schnorr. Process complexity and effective random tests. J. Comput. System Sci., 7:376\u2013388, 1973.","journal-title":"J. Comput. System Sci."},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A. Selman","year":"1979","unstructured":"A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Math. Systems Theory, 13:55\u201365, 1979.","journal-title":"Math. Systems Theory"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:02:33Z","timestamp":1605646953000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}