{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:48:13Z","timestamp":1725468493900},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055796","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"465-473","source":"Crossref","is-referenced-by-count":3,"title":["Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Ambos-Spies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steffen","family":"Lempp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunther","family":"Mainhardt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender, M. Strauss. Measure on small complexity classes with applications for BPP. In Proceedings of the 35th Symposium on Foundations of Computer Science, 867\u2013818, IEEE Computer Society Press, 1994.","DOI":"10.1109\/SFCS.1994.365713"},{"key":"43_CR2","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. Resource-bounded genericity. In Computability, Enumerability, Unsolvability (S. B. Cooper et al., Eds.), London Mathematical Society Lecture Notes Series 224, 1\u201359, Cambridge University Press, 1996.","DOI":"10.1017\/CBO9780511629167.002"},{"key":"43_CR3","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, H. Fleischhack, H. Huwig. Diagonalizations over deterministic polynomial time. In Proceedings of the First Workshop on Computer Science Logic, CSL'87, Lecture Notes in Computer Science 329, 1\u201316, Springer Verlag, 1988.","DOI":"10.1007\/3-540-50241-6_25"},{"key":"43_CR4","first-page":"1","volume":"187","author":"K. Ambos-Spies","year":"1997","unstructured":"K. Ambos-Spies, E. Mayordomo. Resource-bounded measure and randomness. In Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics 187, 1\u201347, Dekker, 1997.","journal-title":"Lecture Notes in Pure and Applied Mathematics"},{"key":"43_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"K. Ambos-Spies, H.-C. Neis, S. A. Terwijn. Genericity and measure for exponential time. Theoretical Computer Science 168 (1996) 3\u201319.","journal-title":"Theoretical Computer Science"},{"key":"43_CR6","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"5","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, R. Solovay. Relativizations of the P =?NP question. SIAM Journal on Computing 5 (1975) 431\u2013442.","journal-title":"SIAM Journal on Computing"},{"key":"43_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennett","year":"1981","unstructured":"C. Bennett, J. Gill. Relative to a random oracle P A \u228b NP A \u228b co-NP A with probability 1. SIAM Journal on Computing 10 (1981) 96\u2013113.","journal-title":"SIAM Journal on Computing"},{"key":"43_CR8","doi-asserted-by":"crossref","unstructured":"H. Buhrman, E. Mayordomo. An excursion to the Kolmogorov random strings. In Proceedings of the 10th IEEE Structure in Complexity Theory Conference, 197\u2013205, IEEE Computer Society Press, 1995.","DOI":"10.1109\/SCT.1995.514858"},{"key":"43_CR9","doi-asserted-by":"crossref","unstructured":"H. Buhrman, D. v. Melkebeek. Hard Sets are Hard to Find. In Proceedings of the 13th IEEE Conference on Comput. Complexity, IEEE Computer Society Press, 1998.","DOI":"10.1109\/CCC.1998.694602"},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"H. Buhrman, D. v. Melkebeek, K. W. Regan, D. Sivakumar, M. Strauss. A generalization of resource-bounded measure with an application. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Springer Verlag, 1998.","DOI":"10.1007\/BFb0028558"},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"S. A. Fenner. Notions of resource-bounded category and genericity. In Proceedings of the 6th IEEE Structure in Complexity Theory Conference, 196-212, IEEE Computer Society Press, 1991.","DOI":"10.1109\/SCT.1991.160262"},{"key":"43_CR12","doi-asserted-by":"publisher","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":"43_CR13","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In Complexity Theory Retrospective II (L.A. Hemaspaandra, A.L. Selman, eds.), Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"43_CR14","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 (1994) 487\u2013506.","journal-title":"Theoretical Computer Science"},{"key":"43_CR15","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics 218, Springer-Verlag, 1971.","DOI":"10.1007\/BFb0112458"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055796","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T14:44:28Z","timestamp":1555771468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055796"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0055796","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}