{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T19:10:03Z","timestamp":1736104203904,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540626169"},{"type":"electronic","value":"9783540683421"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0023487","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T07:06:33Z","timestamp":1132383993000},"page":"535-545","source":"Crossref","is-referenced-by-count":5,"title":["Equivalence of measures of complexity classes"],"prefix":"10.1007","author":[{"given":"Josef M.","family":"Breutzmann","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"44_CR1","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, E. Mayordomo, and X. Zheng. A comparison of weak completeness notions. In Proceedings of the Eleventh IEEE Conference on Computational Complexity. IEEE Computer Society Press, 1996. To appear.","DOI":"10.1109\/CCC.1996.507679"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies, S. A. Terwijn, and X. Zheng. Resource bounded randomness and weakly complete problems. Theoretical Computer Science, 1996. To appear. See also Proceedings of the Fifth Annual International Symposium on Algorithms and Computation, 1994, pp. 369\u2013377. Springer-Verlag.","DOI":"10.1007\/3-540-58325-4_201"},{"key":"44_CR3","doi-asserted-by":"crossref","unstructured":"J. Cai and A. L. Selman. Fine separation of average time complexity classes. In Proceedings of the Thirteenth Symposium on Theoretical Aspects of Computer Science, pages 331\u2013343. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-60922-9_28"},{"issue":"1976","key":"44_CR4","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01084088","volume":"6","author":"R. I. Freidzon","year":"1972","unstructured":"R. I. Freidzon. Families of recursive predicates of measure zero. translated in Journal of Soviet Mathematics, 6(1976):449\u2013455, 1972.","journal-title":"Journal of Soviet Mathematics"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"P. R. Halmos. Measure Theory. Springer-Verlag, 1950.","DOI":"10.1007\/978-1-4684-9440-2"},{"key":"44_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF01206322","volume":"5","author":"D. W. Juedes","year":"1995","unstructured":"D. W. Juedes. Weakly complete problems are not rare. Computational Complexity, 5:267\u2013283, 1995.","journal-title":"Computational Complexity"},{"issue":"2","key":"44_CR7","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(2):279\u2013295, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"44_CR8","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 completeness in E and E2. Theoretical Computer Science, 143:149\u2013158, 1995.","journal-title":"Theoretical Computer Science"},{"key":"44_CR9","doi-asserted-by":"crossref","first-page":"214","DOI":"10.2307\/1969123","volume":"49","author":"S. Kakutani","year":"1948","unstructured":"S. Kakutani. On the equivalence of infinite product measures. Annals of Mathematics, 49:214\u2013224, 1948.","journal-title":"Annals of Mathematics"},{"key":"44_CR10","unstructured":"S. M. Kautz. Personal communication, 1996."},{"key":"44_CR11","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Observations on measure and lowness for \u0394 2 P . Mathematical Systems Theory. To appear. See also Proceedings of the Thirteenth Symposium on Theoretical Aspects of Computer Science, pages 87\u201397. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-60922-9_8"},{"key":"44_CR12","doi-asserted-by":"publisher","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:220\u2013258, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pages 158\u2013175, 1993. Updated version to appear in L.A. Hemaspaandra and A.L. Selman (eds.), Complexity Theory Retrospective II, Springer-Verlag, 1996.","DOI":"10.1109\/SCT.1993.336530"},{"key":"44_CR14","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1137\/S0097539793249700","volume":"24","author":"J. H. Lutz","year":"1995","unstructured":"J. H. Lutz. Weakly hard problems. SIAM Journal on Computing, 24:1170\u20131189, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"44_CR15","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J. H. Lutz","year":"1994","unstructured":"J. H. 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"},{"key":"44_CR16","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"J. H. Lutz","year":"1996","unstructured":"J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: Separating completeness notions if NP is not small. Theoretical Computer Science, 164:141\u2013163, 1996.","journal-title":"Theoretical Computer Science"},{"key":"44_CR17","unstructured":"J. H. Lutz and E. Mayordomo. Genericity, measure, and inseparable pairs, 1996. In preparation."},{"issue":"2","key":"44_CR18","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(2):487\u2013506, 1994.","journal-title":"Theoretical Computer Science"},{"key":"44_CR19","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/3-540-06841-4_70","volume":"14","author":"K. Mehlhorn","year":"1974","unstructured":"K. Mehlhorn. The \u201calmost all\u201d theory of subrecursive degrees is decidable. In Proceedings of the Second Colloquium on Automata, Languages, and Programming, pages 317\u2013325. Springer Lecture Notes in Computer Science, vol. 14, 1974.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"44_CR20","doi-asserted-by":"crossref","unstructured":"J. C. Oxtoby. Measure and Category. Springer-Verlag, second edition, 1980.","DOI":"10.1007\/978-1-4684-9339-9"},{"key":"44_CR21","doi-asserted-by":"crossref","unstructured":"K. W. Regan, D. Sivakumar, and J. Cai. Pseudorandom generators, measure theory, and natural proofs. In 36th IEEE Symposium on Foundations of Computer Science, pages 26\u201335. IEEE Computer Society Press, 1995.","DOI":"10.1109\/SFCS.1995.492459"},{"key":"44_CR22","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr","year":"1967","unstructured":"H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw \u2014 Hill, New York, 1967."},{"key":"44_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00538763","volume":"16","author":"C. P. Schnorr","year":"1970","unstructured":"C. P. Schnorr. Klassifikation der Zufallsgesetze nach Komplexit\u00e4t und Ordnung. Z. Wahrscheinlichkeitstheorie verw. Geb., 16:1\u201321, 1970.","journal-title":"Z. Wahrscheinlichkeitstheorie verw. Geb."},{"key":"44_CR24","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C. P. Schnorr","year":"1971","unstructured":"C. P. Schnorr. A unified approach to the definition of random sequences. Mathematical Systems Theory, 5:246\u2013258, 1971.","journal-title":"Mathematical Systems Theory"},{"key":"44_CR25","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, 218, 1971.","DOI":"10.1007\/BFb0112458"},{"key":"44_CR26","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr. Process complexity and effective random tests. Journal of Computer and System Sciences, 7:376\u2013388, 1973.","journal-title":"Journal of Computer and System Sciences"},{"key":"44_CR27","unstructured":"M. van Lambalgen. Random Sequences. PhD thesis, Department of Mathematics, University of Amsterdam, 1987."},{"key":"44_CR28","first-page":"656","volume":"35","author":"V. G. Vovk","year":"1987","unstructured":"V. G. Vovk. On a randomness criterion. Soviet Mathematics Doklady, 35:656\u2013660, 1987.","journal-title":"Soviet Mathematics Doklady"},{"key":"44_CR29","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1070\/rm1970v025n06ABEH001269","volume":"25","author":"A. K. Zvonkin","year":"1970","unstructured":"A. K. Zvonkin and L. A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25:83\u2013124, 1970.","journal-title":"Russian Mathematical Surveys"}],"container-title":["Lecture Notes in Computer Science","STACS 97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0023487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T18:56:01Z","timestamp":1736103361000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0023487"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540626169","9783540683421"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/bfb0023487","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}