{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:35Z","timestamp":1742617175621,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583387"},{"type":"electronic","value":"9783540486633"}],"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-58338-6_69","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:50:24Z","timestamp":1330271424000},"page":"221-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Genericity and measure for exponential time"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[]},{"given":"Hans-Christian","family":"Neis","sequence":"additional","affiliation":[]},{"given":"Sebastiaan A.","family":"Terwijn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"15_CR1","unstructured":"K. Ambos-Spies, Randomness, relativizations, and polynomial reducibilities, in: Proc. First Structure in Complexity Theory Conference 1986, Lect. Notes Comput. Sci. 223 (1986) 23\u201334, Springer Verlag."},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(87)90053-3","volume":"51","author":"K. Ambos-Spies","year":"1987","unstructured":"K. Ambos-Spies, H. Fleischhack, and H. Huwig, Diagonalizations over polynomial time computable sets, Theor. Comput. Sci. 51 (1987) 177\u2013204.","journal-title":"Theor. Comput. Sci."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, H. Fleischhack, and H. Huwig, Diagonalizing over deterministic polynomial time, in: Proc. CSL '87, Lect. Notes Comput. Sci. 329 (1988) 1\u201316, Springer Verlag.","DOI":"10.1007\/3-540-50241-6_25"},{"key":"15_CR4","unstructured":"K. Ambos-Spies, S. A. Terwijn, X. Zheng, Resource bounded randomness and weakly complete problems (in preparation; a preliminary report is submitted)"},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01699457","volume":"18","author":"J. L. Balcazar","year":"1985","unstructured":"J. L. Balcazar and U. Sch\u00f6ning. Bi-immune sets for complexity classes, Math. Systems Theory 18 (1985) 1\u201310.","journal-title":"Math. Systems Theory"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"C. H. Bennett and J. Gill, relative to a random oracle A, PA\u2260NPA\u2260co-NPA with probability 1, SIAM J. Comput. 10 (1981) 96\u2013113.","journal-title":"SIAM J. Comput."},{"key":"15_CR7","unstructured":"H. Fleischhack, On Diagonalizations over Complexity Classes, Dissertation, Universit\u00e4t Dortmund, Dept. Comput. Sci. Tech. Rep. 210, 1985."},{"key":"15_CR8","unstructured":"H. Fleischhack, P-genericity and strong P-genericity, in: Proc. MFCS 1986, Lect. Notes Comput. Sci. 233 (1986) 341\u2013349, Springer Verlag."},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0019-9958(86)80012-2","volume":"71","author":"H. Heller","year":"1986","unstructured":"H. Heller, On relativized exponential and probabilistic complexity classes, Information and Control 71 (1986) 231\u2013243.","journal-title":"Information and Control"},{"key":"15_CR10","unstructured":"C. Jockusch, Degrees of generic sets, in: Recursion Theory: its Generalisations and Applications, London Math. Soc. Lect. Notes Series 45 (1980) 110\u2013139, Cambridge University Press."},{"key":"15_CR11","unstructured":"D. W. Juedes and J. H. Lutz, The complexity and distribution of hard problems, Tech. Rep. 92-23, Dept. Comput. Sci., Iowa State University. 1992 (submitted for publication)."},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, N. A. Lynch and A. L. Selman, A comparison of polynomial time reduciblities, Theor. Comput. Sc. 1 (1975) 103\u2013123.","journal-title":"Theor. Comput. Sc."},{"key":"15_CR13","unstructured":"W. Lindner, On the polynomial time bounded measure of one-truth-table degrees and p-selectivity, Diplomarbeit, Technische Universit\u00e4t Berlin, 1993."},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J. H. Lutz","year":"1990","unstructured":"J. H. Lutz, Category and measure in complexity classes, SIAM J. Comput. 19 (1990) 1100\u20131131.","journal-title":"SIAM J. Comput."},{"key":"15_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, J. Comput. System Sci. 44 (1992) 220\u2013258.","journal-title":"J. Comput. System Sci."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"J. H. Lutz, The quantitative structure of exponential time, in: Proc. 8th Structure in Complexity Theory Conference, 1993, 158\u2013175, IEEE Coput. Sci. Press.","DOI":"10.1109\/SCT.1993.336530"},{"key":"15_CR17","unstructured":"J. H. Lutz and E. Mayordomo, Measure, stochasticity, and the density of hard languages, SIAM J. Comput. (to appear)."},{"key":"15_CR18","unstructured":"J. H. Lutz and E. Mayordomo, Cook versus Karp-Levin: Separating completeness notions if NP is not small. Tech. Rep. 92-24, Dept. Comput. Sci., Iowa State University. 1992. [Extended Abstract in: Proc. STACS 94, Lect. Notes Comput. Sci. 775 (1994) 415\u2013426, Springer Verlag.]"},{"key":"15_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 (1966) 602\u2013619.","journal-title":"Information and Control"},{"key":"15_CR20","unstructured":"E. Mayordomo, Almost every set in exponential time is P-bi-immune, in: Proc. MFCS 1992, Lect. Notes Comput. Sci. 629 (1992) 392\u2013400, Springer Verlag."},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr, Zuf\u00e4lligkeit und Wahrscheinlichkeit, Lect. Notes Mathematics 218, 1971, Springer Verlag.","DOI":"10.1007\/BFb0112458"},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(91)90314-R","volume":"81","author":"S. Tang","year":"1991","unstructured":"S. Tang and R. Book, Polynomial-time reducibilities and \u201calmost all\u201d oracle sets, Theor. Comput. Sci 81 (1991) 35\u201347.","journal-title":"Theor. Comput. Sci"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1994"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58338-6_69","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:26:57Z","timestamp":1742596017000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58338-6_69"}},"subtitle":["Extended Abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583387","9783540486633"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-58338-6_69","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":"4 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}