{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:49Z","timestamp":1725663649945},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_6","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:17:15Z","timestamp":1330255035000},"page":"38-47","source":"Crossref","is-referenced-by-count":3,"title":["Measure, stochasticity, and the density of hard languages"],"prefix":"10.1007","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]},{"given":"Elvira","family":"Mayordomo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"6_CR1","unstructured":"N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1992."},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"V. Arvind, J. K\u00f6bler, and M. Mundhenk, Bounded truth-table and conjunctive reductions to sparse and tally sets, Technical report. University of Ulm, 1992. Technical Report Ulmer Informatik-Berichte 92-01.","DOI":"10.1007\/3-540-56287-7_101"},{"key":"6_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis, On isomorphism and density of NP and other complete sets, SIAM Journal on Computing 6 (1977), pp. 305\u2013322.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u00f6s","year":"1947","unstructured":"P. Erd\u00f6s, Some remarks on the theory of graphs, Bulletin of the American Mathematical Society 53 (1947), pp. 292\u2013294.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"6_CR5","volume-title":"Probabilistic Methods in Combinatorics","author":"P. Erd\u00f6s","year":"1974","unstructured":"P. Erd\u00f6s and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press, New York, 1974."},{"key":"6_CR6","unstructured":"B. Fu, With quasi-linear queries EXP is not polynomial time Turing reducible to sparse sets, manuscript, August 1992."},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"L. A. Hemachandra, M. Ogiwara, and O. Watanabe, How hard are sparse sets?, Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992, pp. 222\u2013238. IEEE Press.","DOI":"10.1109\/SCT.1992.215396"},{"key":"6_CR8","unstructured":"D. W. Juedes and J. H. Lutz, The complexity and distribution of hard problems, Technical Report 92-23, Department of Computer Science, Iowa State University, 1992. Submitted."},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"D. W. Juedes and J. H. Lutz, Kolmogorov complexity, complexity cores, and the distribution of hardness, In O. Watanabe, editor, Kolmogorov Complexity and Computational Complexity. Springer-Verlag, 1992, pp. 43\u201365.","DOI":"10.1007\/978-3-642-77735-6_4"},{"key":"6_CR10","unstructured":"R. M. Karp and R. J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 302\u2013309, also published as Turing machines that take advice, L'Enseignement Mathematique 28 (1982), pp. 191\u2013209."},{"key":"6_CR11","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1137\/1132060","volume":"32","author":"A. N. Kolmogorov","year":"1987","unstructured":"A. N. Kolmogorov and V. A. Uspenskii, Algorithms and randomness, translated in Theory of Probability and its Applications 32 (1987), pp. 389\u2013412.","journal-title":"Theory of Probability and its Applications"},{"key":"6_CR12","unstructured":"J. H. Lutz, Intrinsically pseudorandom sequences, in preparation."},{"key":"6_CR13","unstructured":"J. H. Lutz, Resource-bounded measure, in preparation."},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0304-3975(91)90320-2","volume":"81","author":"J. H. Lutz","year":"1991","unstructured":"J. H. Lutz, An upward measure separation theorem, Theoretical Computer Science 81 (1991), pp. 127\u2013135.","journal-title":"Theoretical Computer Science"},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J. H. Lutz","year":"1992","unstructured":"J. H. Lutz, Almost everywhere high nonuniform complexity, Journal of Computer and System Sciences 44 (1992), pp. 220\u2013258.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR16","unstructured":"J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. Technical Report 92-11, Department of Computer Science, Iowa State University, 1992. Submitted."},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"J. H. Lutz and W. J. Schmidt, Circuit size relative to pseudorandom oracles, Theoretical Computer Science A 107 (1993), to appear.","DOI":"10.1016\/0304-3975(93)90256-S"},{"key":"6_CR18","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. R. Mahaney","year":"1982","unstructured":"S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, Journal of Computer and System Sciences 25 (1982), pp. 130\u2013143.","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"E. Mayordomo, Almost every set in exponential time is P-bi-immune, Seventeenth International Symposium on Mathematical Foundations of Computer Science, 1992. Springer-Verlag, to appear.","DOI":"10.1007\/3-540-55808-X_38"},{"key":"6_CR20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"A. R. Meyer","year":"1977","unstructured":"A. R. Meyer, 1977, reported in [3].","journal-title":"SIAM Journal on Computing"},{"key":"6_CR21","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 bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing 20 (1991), pp. 471\u2013483.","journal-title":"SIAM Journal on Computing"},{"key":"6_CR22","unstructured":"A. L. Selman, 1992, personal communication."},{"key":"6_CR23","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C. E. Shannon","year":"1948","unstructured":"C. E. Shannon, A mathematical theory of communication, Bell System Technical Journal 27 (1948), pp. 379\u2013423, 623\u2013656.","journal-title":"Bell System Technical Journal"},{"key":"6_CR24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"C. E. Shannon","year":"1949","unstructured":"C. E. Shannon, The synthesis of two-terminal switching circuits, Bell System Technical Journal 28 (1949), pp. 59\u201398.","journal-title":"Bell System Technical Journal"},{"key":"6_CR25","unstructured":"J. H. Spencer, Ten Lectures on the Probabilistic Method, SIAM, 1987."},{"key":"6_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1977), pp. 1\u201322.","journal-title":"Theoretical Computer Science"},{"key":"6_CR27","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1070\/RM1990v045n01ABEH002321","volume":"45","author":"V. A. Uspenskii","year":"1990","unstructured":"V. A. Uspenskii, A. L. Semenov, and A. Kh. Shen', Can an individual sequence of zeros and ones be random?, Russian Mathematical Surveys 45 (1990), pp. 121\u2013189.","journal-title":"Russian Mathematical Surveys"},{"key":"6_CR28","unstructured":"O. Watanabe, On the Structure of Intractable Complexity Classes, PhD thesis, Tokyo Institute of Technology, 1987."},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"O. Watanabe, Polynomial time reducibility to a set of small density, Proceedings of the Second Structure in Complexity Theory Conference, 1987, pp. 138\u2013146.","DOI":"10.1109\/PSCT.1987.10319263"},{"key":"6_CR30","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"C. B. Wilson, Relativized circuit complexity, Journal of Computer and System Sciences 31 (1985), pp. 169\u2013181.","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T14:51:29Z","timestamp":1713624689000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}